Metraipolis › archive › dc_d57510106c73
Minimising the harmonic sum of cycle lengths — arXiv:2609.26401
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.26401
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-08T15:56:04.598Z
- SHA-256 of the archived text
cc2ed6b41748b5e938fb4cf6b6cbbd8e0a74aaa7addaed2aeef7654b253ca6e1- Stable URL of this page
https://metraipolis.com/documento/dc_d57510106c73
How to cite
Minimising the harmonic sum of cycle lengths — arXiv:2609.26401 — arXiv (en), https://arxiv.org/abs/2609.26401 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_d57510106c73 (Metraipolis archive dc_d57510106c73, sha256 cc2ed6b41748b5e938fb4cf6b6cbbd8e0a74aaa7addaed2aeef7654b253ca6e1)
BibTeX
@misc{dcd57510106c73,
title = {Minimising the harmonic sum of cycle lengths — arXiv:2609.26401},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.26401},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_d57510106c73; sha256 cc2ed6b41748b5e938fb4cf6b6cbbd8e0a74aaa7addaed2aeef7654b253ca6e1},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.26401. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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):=\sum_{\ell\in{C}(G)}1/\ell$ 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\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 2k$ satisfies $s(G)\geq\sum_{\ell=2}^{k}1/(2\ell)$. 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.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-23 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.26401 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T15:16:21.699Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).