Optimal cycle count bound via edge number
Conjecture 2 · arXiv:1907.12091
Status open high confidence
Conjecture 2 from arXiv:1907.12091 asserts that every simple graph with $m$ edges has at most $O(\kappa_1^m)$ cycles, where $\kappa_1 = (2+2\sqrt{2})^{1/5} \approx 1.3701$, matching the Arman–Tsaturian lower bound. The source paper itself resolved several conjectures of Király and Arman–Tsaturian, but Conjecture 2 — that the Arman–Tsaturian construction is tight — was left open. No subsequent paper proving or disproving this conjecture was found in a targeted web search; the best known upper bound for the number of cycles in a simple graph with $m$ edges remains approximately $1.443^m$, leaving a significant gap.
Reviewer notes. No follow-up resolving Conjecture 2 was found. The Arman–Tsaturian construction (arXiv:1702.02662, EJC 2019) provides the best known lower bound $\Omega(\kappa_1^m)$. The source paper improves the upper bound and resolves several related conjectures, but the precise constant for simple graphs remains open. Any counterexample would necessarily have average degree in $(4.24, 7.18)$ per Remark 9 of the source paper.
Context
The Arman–Tsaturian construction [2] gives simple graphs with $\Omega(\kappa_1^m)$ cycles, which is the best known lower bound. The authors verified by computer several similar constructions and could not find a better one, leading them to conjecture that this construction is optimal. Remark 9 notes that any counterexample would necessarily have average degree in the range $(4.24, 7.18)$.
Notes. PDF source — math may be garbled; value of $\kappa_1$ reconstructed from surrounding prose.
Source paper
Bounding the number of cycles in a graph in terms of its degree sequence
Zdeněk Dvořák, Natasha Morrison, Jonathan A. Noel, Sergey Norin, Luke Postle · 2019-07-28
https://arxiv.org/abs/1907.12091
PDF source