For every pair of integers n,k with 2≤ k≤ n/2, and every n-vertex graph G satisfying e(G)≥ k(n-k), define C(G) to be the set of cycle lengths occurring in G and s(G):=∑_ell∈C(G)frac1ell. Then s(G)≥ s(K_k,n-k)=∑_i=2^kfrac12i; equivalently, K_k,n-k minimizes s(G) among all n-vertex graphs with at least k(n-k) edges.

Erdős’s harmonic cycle-length conjecture

Erdős’s conjecture predicts that sufficiently dense graphs have a reciprocal cycle-length sum at least that of the corresponding complete bipartite graph. The newly reported result establishes this only in the large-parameter regime and gives uniqueness of the extremal graph there.

Known results

Gyárfás, Komlós, and Szemerédi proved a lower bound of order $\log d$ for graphs of average degree $d$ .
A later paper claimed the asymptotically sharp bound $\left(\frac{1}{2}-o_d(1)\right)\log d$ , matching balanced complete bipartite graphs asymptotically.

September 2026 large-parameter result

On September 22, 2026, Montgomery, Milojević, Pokrovskiy, and Sudakov reported that every sufficiently large graph above the relevant edge threshold has reciprocal cycle-length sum at least the complete-bipartite benchmark, with equality uniquely attained by that complete bipartite graph. This is claimed progress, not a full resolution: the finite-parameter range remains open.

Current status (as of September 2026): The conjecture is claimed for sufficiently large parameters with a unique extremal graph, while the full range of $k$ remains open.

Erdős’s harmonic cycle-length conjecture

Primary source

Additional references

Progress summary

Solutions 0