Erdős Problem #72

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 [Bo77] proved that such a \(c\) does exist if \(A\) is an infinite arithmetic progression containing even numbers (see [71](https://www.erdosproblems.com/71)). Erdős was 'almost certain' that if \(A\) is the set of powers of \(2\) then no such \(c\) exists (although he conjectured 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.