Minimizing the harmonic sum of cycle lengths

An old conjecture of Erdös and Hajnal[1] concerns cycle lengths in a graph:

Conjecture (proposed by Erdös and Hajnal[1])

For a graph \(G\) on \(n\) vertices, let \(3 \leq r_1 < r_2 < \ldots < r_t \leq n\) be the set of integers \(r\) for which \(G\) contains a cycle \(C_r\). Determine or estimate \[ f(k)=\inf \sum \frac 1 {r_i} \] where the infimum ranges over all graphs on \(n\) vertices and at least \( k n \) edges.

Gyárfás, Komlós and Szemerédi[2] proved that

\(\displaystyle \sum \frac 1 {r_i} \geq c \log \delta \)

for a graph with minimum degree \( \delta\). Gyárfás, Prömel, Szemerédi and Voigt [3] proved that

\(\displaystyle f(1+\frac 1 {\alpha}) \geq \frac 1 {300 \alpha \log \alpha}. \)

This implies that sparse graphs of large girth must contain many cycles of different lengths.

Bibliography
1 P. Erdös, Some recent progress on extremal problems in graph theory, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), Congress. Numer. XIV, 3-14, Utilitas Math., Winnipeg, Man., 1975.

2 A. Gyárfás, J. Komlós and A. Szemerédi, On the distribution of cycle lengths in graphs, J. Graph Theory 8 (1984), 441-462.

3 A. Gyárfás, H. J. Prömel, E. Szemerédi and B. Voigt. On the sum of the reciprocals of cycle lengths in sparse graphs. Combinatorica 5 (1985), 41-52.