Erdős Problem #72

Erdős Problem 72: a sparse unavoidable set of cycle lengths

1) Statement and construction

Does there exist a set $A\subseteq\mathbb N$ of density zero and a constant $c$ such that every sufficiently large finite graph of average degree at least $c$ has a cycle with length in $A$? Take the explicit set \[ A=\{2^j:j\geq2\}. \] The assertion for this set follows from a theorem of Liu and Montgomery, strengthening Verstraete's earlier existence result. We use that theorem explicitly and prove the numerical deduction.

2) External theorem and the required uniform constant

Theorem 1.1 of Liu--Montgomery gives $d_0$ such that every graph of average degree $d\geq d_0$ has a number \[ \ell\geq\frac{d}{10(\log d)^{12}} \] with cycles of every even length in $[(\log\ell)^8,\ell]$. Choose $L\geq4$ so large that $(\log x)^8\leq x/2$ for all $x\geq L$. Then choose $c\geq d_0$ so large that $d/[10(\log d)^{12}]\geq L$ whenever $d\geq c$. Both choices are possible by the elementary comparison between powers of logarithm and positive powers of $x$.

Let $G$ have average degree at least $c$, and take the corresponding $\ell$. If $j=\lfloor\log_2\ell\rfloor$, then \[ \ell/2<2^j\leq\ell, \qquad 2^j\geq4, \qquad 2^j\geq(\log\ell)^8. \] Thus $2^j$ is one of the even cycle lengths supplied by the theorem. It belongs to $A$, as required. In fact this argument works for every finite graph meeting the average-degree threshold, without an additional lower bound on its order.

3) Density and a useful extension

For $N\geq4$, \[ |A\cap[1,N]|=\lfloor\log_2N\rfloor-1, \qquad \frac{|A\cap[1,N]|}{N}\longrightarrow0. \] Hence the chosen set really has natural density zero; no appeal to its complement being large is needed.

More generally, let $a_1<a_2<\cdots$ be even integers with $a_{j+1}\leq K a_j$ for some fixed $K>1$. For sufficiently large $\ell$, take the largest $a_j\leq\ell$. Then $\ell<a_{j+1}\leq K a_j$, so $a_j>\ell/K$. Once $(\log\ell)^8\leq\ell/K$ and $\ell\geq a_1$, the same interval theorem forces a cycle length from this sequence. This explains why exponential sparsity is compatible with being unavoidable.

Outcome: SOLVED, known affirmative resolution reconstructed using the stated external theorem. The theorem's graph-theoretic proof is not supplied or independently formally verified here.

4) Sources

• H. Liu and R. Montgomery, A solution to Erdős and Hajnal's odd cycle problem, Theorem 1.1, https://arxiv.org/abs/2010.15802.
• T. F. Bloom, Problem 72, https://www.erdosproblems.com/72, checked 23 September 2026.

The estimate measures coverage using the explicitly cited theorem, not novelty of the construction.

5) COMPLETION ESTIMATE

COMPLETION: 100%