Erdős Problem #72
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: graph theory, cycles.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Can one name a very sparse set of cycle lengths that must nevertheless occur in any sufficiently dense graph? Erdős #72 asks for a set \(A\subset\mathbb N\) of natural density zero and a constant \(c>0\) such that every sufficiently large graph with average degree at least \(c\) contains a cycle whose length lies in \(A\).
A set has density zero when the fraction of integers up to \(N\) belonging to it tends to zero. This makes the question striking: although almost every positive integer is excluded, one of the few permitted lengths is unavoidable.
A small example
Consider the powers of two \(A=\{4,8,16,\ldots\}\). At most \(\lfloor\log_2N\rfloor\) elements of \(A\) are at most \(N\). Hence
The complete bipartite graph \(K_{4,4}\) has cycles of lengths \(4\) and \(8\), both in \(A\). This is an illustration only; finite examples do not prove a statement about every graph above a density threshold.
What is known
The answer is YES. Verstraëte proved that some density-zero set is unavoidable, using a nonconstructive existence argument. More strongly, Liu and Montgomery showed that even the explicit powers-of-two sequence works. Their Corollary 1.3 states that an increasing sequence of even integers \(\sigma_i\) satisfying
at every index is unavoidable once the average degree reaches a fixed threshold depending on the first term and a universal constant. A sufficiently late tail of the powers of two satisfies this inequality; the first few powers do not. For \(\sigma_i=2^{J+i}\) and sufficiently large \(J\), the condition is fulfilled because \(2\sigma_i\le\exp(\sigma_i^{1/10})\) eventually. The tail is still density zero and supplies one fixed \(A\) and one fixed \(c\).
The deep cycle-length theorem supplies the universal graph implication, not the elementary density calculation.
GCL's current state
GCL checked Theorem 1.1 and Corollary 1.3 against the authors' primary 2022 arXiv revision, including the growth condition and its starting-index subtlety. The source classification is PROVED. Original assignment #1341 has an authenticated source return. This remains a pending local article, not mathematical certification or acceptance.
The original GitHub issue now contains the authenticated RESULT/1 source report. This does not imply independent mathematical review or editorial admission.
What remains
An explicit choice is \(J=60\): \(2^{6}=64>61\log2\), equivalently \(2\cdot2^{60}<\exp((2^{60})^{1/10})\). Moreover, \(2^{j/10}/(j+1)\) increases for integers \(j\ge60\), so every later power satisfies the same inequality. Then instantiate the published corollary with the tail and prove the density-zero bound. Do not silently apply the corollary to the sequence starting at \(4\), where its quantified hypothesis fails.
Sources and claim boundaries
- Liu–Montgomery, A solution to Erdős and Hajnal's odd cycle problem, Theorem 1.1 and Corollary 1.3, arXiv:2010.15802v2 (19 September 2022), primary theorem statement directly checked, full proof not independently replayed.
- Erdős problem #72, pinned catalogue revision 536408716724a2402bdfa7c1d764bf83d64a8c89.
- Original source issue #1341.
No new GCL theorem, formal certification or editorial admission is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1341 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.