Skip to content

Erdős Problem #65

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

A graph can contain cycles of many lengths. Erdős and Hajnal asked how large the sum of the reciprocals of those different lengths must be when a graph has many edges. They also asked which graphs make that sum as small as possible.

If a graph has \(n\) vertices and \(kn\) edges, let \(\mathcal C(G)\) be its set of distinct simple-cycle lengths. The quantity is

\[ R(G)=\sum_{\ell\in\mathcal C(G)}\frac1\ell. \]

A small example

The balanced complete bipartite graph \(K_{m,m}\) has \(2m\) vertices, \(m^2\) edges, and every even cycle length \(4,6,\ldots,2m\), with no odd cycles. Therefore

\[ R(K_{m,m})=\frac14+\frac16+\cdots+\frac1{2m} =\frac12(H_m-1) =\frac12\log m+O(1). \]

Here \(H_m=1+1/2+\cdots+1/m\). Since \(k=m/2\), this example has the leading growth \((1/2)\log k\). Counting cycles rather than distinct cycle lengths would give a different, incorrect sum.

What is known

The lower-bound question is solved. Gyárfás, Komlós and Szemerédi proved logarithmic growth. Liu and Montgomery sharpened the bound: if \(d\) is the average degree, then

\[ R(G)\ge\left(\frac12-o_d(1)\right)\log d. \]

This is their Corollary 1.2, derived from a theorem guaranteeing long intervals of even cycle lengths in sufficiently dense graphs. As \(d=2k\), it matches the leading constant exhibited by balanced complete bipartite graphs.

The exact extremal characterization is a separate question. A new primary preprint by Montgomery, Milojević, Pokrovskiy and Sudakov, Minimising the harmonic sum of cycle lengths, submitted 22 September 2026, proves a large-parameter version of Erdős's conjecture. Write \(q\) for the preprint's integer parameter, distinct from the original density \(k=e(G)/n\). For all sufficiently large \(q\), if \(n\ge2q\) and \(e(G)>(q-1)(n-q+1)\), the authors assert

\[ R(G)\ge\sum_{\ell=2}^{q}\frac1{2\ell}. \]

For \(e(G)\ge q(n-q)\), equality occurs uniquely at \(K_{q,n-q}\). The authors' abstract confirms that complete bipartite graphs minimise, not maximise, this quantity. The maintained catalogue's note saying "maximised" reverses the direction. The September 2026 preprint does not automatically settle every smaller parameter or variant of the original edge-density formulation.

GCL's current state

The pinned catalogue and maintained Erdős #65, last edited February 2026, mark the extremal question OPEN; both predate the September 2026 preprint. GCL verified the complete-bipartite harmonic example and inspected the new authors' theorem claim in its abstract. The complete proof has not been independently audited, and the unrestricted historical status requires careful reconciliation. The original assignment is #1334. This remains an unaccepted local draft.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

Inspect the full September 2026 paper and verify its exact theorem, equality and threshold conditions. Map its integer \(q\) to the original \(k=e(G)/n\) without losing quantifiers, and identify any finite or alternative-constraint remainder. Formalize the elementary cycle-length classification for \(K_{m,m}\). The minimum/maximum wording conflict is resolved by the new primary abstract, not by editorial speculation.

Sources and claim boundaries

No new GCL proof, independent verification of the 2026 preprint, all-parameter resolution or editorial acceptance is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1334 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: FORMAL_SOURCE_REFRESH_REQUIRED.
  • 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.

Back to catalogue · Compendium introduction