## Keywords (2)

Publications
Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation

# Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation,10.1112/blms/bdp126,Bulletin of The London Mathematical Socie

Two Erdos problems on lacunary sequences: Chromatic number and Diophantine approximation
Let ${n_k}$ be an increasing lacunary sequence, i.e., $n_{k+1}/n_k>1+r$ for some $r>0$. In 1987, P. Erdos asked for the chromatic number of a graph $G$ on the integers, where two integers $a,b$ are connected by an edge iff their difference $|a-b|$ is in the sequence ${n_k}$. Y. Katznelson found a connection to a Diophantine approximation problem (also due to Erdos): the existence of $x$ in $(0,1)$ such that all the multiples $n_j x$ are at least distance $\delta(x)>0$ from the set of integers. Katznelson bounded the chromatic number of $G$ by $Cr^{-2}|\log r|$. We apply the Lov\'asz local lemma to establish that $\delta(x)>cr|\log r|^{-1}$ for some $x$, which implies that the chromatic number of $G$ is at most $Cr^{-1} |\log r|$. This is sharp up to the logarithmic factor.
Journal: Bulletin of The London Mathematical Society - BULL LOND MATH SOC , vol. 42, no. 2, pp. 295-300, 2010
View Publication
 The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
 ( blms.oxfordjournals.org ) ( arxiv.org ) ( www.math.uchicago.edu )

## Citation Context (3)

• ...result, Theorem 1.1, was obtained in 1999 and presented in a lecture [14] at the IAS, Princeton...

### Yuval Peres, et al. Two Erdos problems on lacunary sequences: Chromatic number and Diophan...

• ...It seems that essentially the same special case was used by Peres and Schlag in their paper on Lacunary sequences [19]...

### Wesley Pegden. Highly nonrepetitive sequences: winning strategies from the local lemm...

• ...Those methods can be applied even if the rational number p/q is replaced by an arbitrary real number a> 1. See, e.g., some recent work [1,4,7,12] on this problem...

## References (12)

### The Probabilistic Method(Citations: 2202)

Published in 1992.

### Chromatic Numbers of Cayley Graphs on Z and Recurrence(Citations: 11)

Journal: Combinatorica , vol. 21, no. 2, pp. 211-219, 2001

### Distance Graphs with Finite Chromatic Number(Citations: 14)

Journal: Journal of Combinatorial Theory - JCT , vol. 85, no. 1, pp. 181-187, 2002

### PROBLEMS AND RESULTS ON 3CHROMATIC HYPERGRAPHS AND SOME RELATED QUESTIONS(Citations: 143)

Published in 1975.

### Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions(Citations: 212)

Journal: Journal D Analyse Mathematique - J ANAL MATH , vol. 31, no. 1, pp. 204-256, 1977
Sort by: