Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be a graph with vertices and edges, and be the lengths of cycles in . Is it true that
Is the sum minimised when is a complete bipartite graph?
Source: erdosproblems.com/65
No claim settles this problem.
Open: the site labels the problem OPEN (page last edited 8
February 2026), and the frontmatter standing is derived from the three claim
pages under claims/, all partial, the two questions being its parts. The
first question is settled: Gyárfás, Komlós and Szemerédi's refereed theorem
gives
(claim page (Gyárfás, Komlós and Szemerédi, 1984),
accepted, settling the part harmonic_bound), and Liu and Montgomery's
refereed Corollary 1.2 gives the asymptotically sharp constant for
large
(claim page (Liu Montgomery, 2020),
accepted). The second question is open: Milojević, Montgomery, Pokrovskiy
and Sudakov's arXiv preprint of 22 September 2026 claims the complete
bipartite minimizer for every sufficiently large
(claim page (Milojević, Montgomery, Pokrovskiy and Sudakov, 2026),
claimed), and nothing covers small , so the standing is open. The site's
commentary credits the first question to [GKS84] and the sharp constant to
[LiMo20], and mentions the forthcoming work through Montgomery's survey.