Home » Combinatorics » Erdos problems on lacunary sequences

Erdos problems on lacunary sequences

The chromatic number $\chi(G)$ of a graph $G$ is the minimal number of colors in a proper vertex coloring
(neighbors assigned distinct colors.)

Problem A (Erdos, 1987):
Fix $\epsilon>0$ and suppose $\{n_j\}_{j=1}^\infty$ is a lacunary sequence of
positive integers, where $n_{j+1}>(1+\epsilon) n_j$ for all $j \ge 1$ .

Is the chromatic number~ $\chi(G)$ necessarily finite?

Problem B (Erdos, 1975):
Let $\eps>0$ and let $\{n_j\}_{j=1}^{\infty}$ be as in Problem A.
Is there a number $\theta\in(0,1)$ so that the sequence
$\{n_j \theta\}_{j=1}^\infty$ is not dense modulo $1$ ?

The answer to both problems is positive. Indeed, if the distance from $n_j \theta$ to the nearest integer is at least $\delta$ for all $j$ , then $\chi(G) \le 1+1/\delta$ .

Khinchin, and independently, Katznelson, proved a lower bound of $\epsilon^{-2}$ for $\delta$ , and this was improved to $\epsilon/(|\log \epsilon|)$ by Peres and Schlag. Is the logarithmic term needed?

REFERENCES

Erdos problems on lacunary sequences

Send me questions about this open problem

Contact Me