Skip to content
DraconiticResearch
Search Sources API
201,642 studies31 sourcesUpdated 13 min ago
PreprintCC BY 4.0arXiv

Minimising the harmonic sum of cycle lengths

  • Richard Montgomery
  • Aleksa Milojević
  • Alexey Pokrovskiy
  • Benny Sudakov
Open at sourcePDFDOICite

Abstract

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ős and Hajnal suggested studying s(G):=∑ℓ∈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ő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 Kk, n−k minimises s(G) among all n-vertex graphs with at least k(n−k) edges (where k≤ 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≥ 2k satisfies s(G)≥∑ℓ=2k1/(2ℓ). Moreover, we show that the complete bipartite graph Kk,n−k is the unique graph with at least k(n−k) edges that achieves equality here.

Related

  1. A brief introduction to the regularity theory of minimising harmonic maps
    Siran Li
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  2. Extremal graphs with cycle lengths in a fixed residue class
    Takahiro Ueoro
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  3. The Erdős-Gallai bound for consecutive even cycle lengths
    Yaobin Chen, Hong Liu, Xia Wang +2
    arXivPreprintCC BY-NC-SA 4.0Full textCombinatorics & discrete mathematicsarXiv
  4. A p-adic Valuation Calculus for Permutations with Restricted Cycle Lengths
    Ahaan Kallat
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv
  5. A minimising principle for interval covers of zigzag persistence modules
    Junyan Chu, Shizuo Kaji, Meiyan Kang
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv

Cite

BibTeXRIS
BibTeX
@misc{montgomery2026minimising,
  title = {{Minimising the harmonic sum of cycle lengths}},
  author = {Richard Montgomery and Aleksa Milojević and Alexey Pokrovskiy and Benny Sudakov},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.26401},
  eprint = {2609.26401},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.26401},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Minimising the harmonic sum of cycle lengths
AU  - Richard Montgomery
AU  - Aleksa Milojević
AU  - Alexey Pokrovskiy
AU  - Benny Sudakov
PY  - 2026
DA  - 2026/09/22
PB  - arXiv
DO  - 10.48550/arxiv.2609.26401
UR  - https://arxiv.org/abs/2609.26401
AB  - 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ős and Hajnal suggested studying s(G):=∑_ℓ∈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ő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≤ 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≥ 2k satisfies s(G)≥∑_ℓ=2^k1/(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.
ER  -