Two Erdős problems on lacunary sequences: Chromatic number and Diophantine approximation

By Yuval Peres, Wilhelm Schlag. 2007

63 citations recorded by the source corpus.

Let {nk} be an increasing lacunary sequence, that is, nk + 1/nk > 1 + ϵ for some ϵ > 0. In 1987, P. Erdős asked for the chromatic number χ(G) of a graph G with vertex set ℤ, where two integers x, y ∈ ℤ are connected by an edge if and only if their difference |x − y| is in the sequence {nk}. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdős): the existence of θ ∈ (0, 1) such that all the multiples nj θ are at a least distance δ(θ) > 0 from ℤ. Katznelson showed that χ(G) ⩽ Cϵ −2|log ϵ|. We apply the Lovász local lemma to establish that δ(θ) > cϵ |log ϵ|−1 for some θ, which implies that χ(G) < Cϵ−1 |log ϵ|. This is sharp up to the logarithmic factor.

Subfields: Algebra and Number Theory, Discrete Mathematics and Combinatorics, Mathematical Physics

View Paper: https://www.semanticscholar.org/paper/1d1228f417c3a53a465f655f5627d3f05d2f1f5b