Logo
All Random Solved Random Open
SOLVED - $100
Is there a set $A\subset \mathbb{N}$ of density $0$ and a constant $c>0$ such that every graph on sufficiently many vertices with average degree $\geq c$ contains a cycle whose length is in $A$?
Bollobás proved that such a $c$ does exist if $A$ is an infinite arithmetic progression containing even numbers. Erdős was 'almost certain' that if $A$ is the set of powers of $2$ then no such $c$ exists (although conjectures that $n$ vertices and average degree $\gg (\log n)^{C}$ suffices for some $C=O(1)$). If $A$ is the set of squares (or the set of $p\pm 1$ for $p$ prime) then he had no guess.

Solved by Verstraëte [Ve05], who gave a non-constructive proof that such a set $A$ exists.

Liu and Montgomery [LiMo20] proved that in fact this is true when $A$ is the set of powers of $2$ (more generally any set of even numbers which doesn't grow too quickly) - in particular this contradicts the previous belief of Erdős.

See also the entry in the graphs problem collection.

Additional thanks to: Richard Montgomery