Minimising the harmonic sum of cycle lengths

Richard Montgomery; Aleksa Milojevi\'c; Alexey Pokrovskiy; Benny Sudakov

In the authors' words

A central theme in extremal graph theory is to understand the relationship between the density of a graph and the richness of its cycle length spectrum, which is the set of distinct cycle lengths occurring in the graph. In 1966, Erd\H{o}s and Hajnal suggested studying $s (G) := \sum_{ℓ \in C (G)} 1/ ℓ$ as a measure of the richness of the cycle length spectrum $C (G)$ of a graph $G$ . Through a series of increasingly strong conjectures, Erd\H{o}s suggested that the complete bipartite graphs minimise $s (G)$ among all graphs $G$ with the same average degree. The sharpest such conjecture, from 1981, states that the graph $K_{k, n - k}$ minimises $s (G)$ among all $n$ -vertex graphs with at least $k (n - k)$ edges (where $k \leq n /2$ ). We prove this conjecture for all sufficiently large $k$ , by showing the stronger statement that any $n$ -vertex graph $G$ with $e (G) > (k - 1) (n - k + 1)$ and $n \geq 2 k$ satisfies $s (G) \geq \sum_{ℓ = 2}^{k} 1/ (2 ℓ)$ . Moreover, we show that the complete bipartite graph $K_{k, n - k}$ is the unique graph with at least $k (n - k)$ edges that achieves equality here.

Main resultLimitation the authors admit

Minimising the harmonic sum of cycle lengths

In the authors' words

More on Combinatorics & discrete math that day

Simple symmetric Venn diagrams with 17 and 19 curves

Graphs with Minimum Algebraic Connectivity I: Proofs of Aldous-Fill and Guiduli-Mohar Conjectures

Lower Bounds for all List-Decodable Deletion Codes

Asymmetric Homomorphism Thresholds for Graphs of Large Odd Girth

Stable Regularity Lemmas: Efficient Algorithms and Essentially Tight Littlestone Bounds