Problem 65

Erdős Problem #65: declared status 'open'. Formalized: no. Let $G$ be a graph with $n$ vertices and $kn$ edges, and $a_1<a_2<\cdots$ be the lengths of cycles in $G$. Is it true that$$\sum\frac{1}{a_i}\gg \log k?$$Is the sum $\sum\frac{1}{a_i}$ minimised when $G$ is a complete bipartite graph? Current best: Liu and Montgomery [LiMo20] have proved the asymptotically sharp lower bound of $\geq (\tfrac{1}{2}-o(1))\log k$. Prize: no. Tags: cycles, graph theory.