Goodman-type lower bounds for odd cycles I: The dense regime
Abstract
Goodman proved a lower bound on triangle counts which, in graphon language, states that every graphon of edge density p has triangle density at least 2p2−p. Bennett, Dudek, Lidický, and Pikhurko established the corresponding bound for C5, determining its minimum density at every Turán density p=1−1/k with an integer k≥3. We extend this bound to every odd cycle in the dense regime: for every odd integer m≥3 and every graphon W with edge density p≥2/3, t(Cm, W) ≥ pm−p(1−p)m−1. For 2/3≤ p<1, equality holds precisely for balanced complete k-partite graphons with an integer k≥3, up to graphon equivalence, and we establish qualitative stability at these densities. In the same density range, we also strengthen Kim and Lee's density-sensitive commonality inequality for odd cycles by adding the nonnegative term t(Pm−1,1−W)−(1−p)m−1 to the lower bound, where Pm−1 is the path with m−1 edges. To prove the main results, we develop a spectral excursion expansion and use Dirichlet averaging to reduce the resulting polynomial inequalities in arbitrarily many spectral variables to a one-variable problem. We prove the one-variable inequality through a uniform inequality comparing odd and even moments of shifted Gamma random variables. We also formalise the odd-cycle lower-bound theorem in Lean 4.
Related
- Small graphs without power-of-two cycles: a lower bound of 24, a correction to a construction of Exoo, and explicit bounds for f(k)
- Information Lower Bound for Regime Boundary Estimation — Optimal Precision Limit at the n² Scale and Universal Constant c=1/8 in the Fixed-Breakpoint Model
- Mathematical Classification of Switching Types and Hierarchical Structures: Three Switching Types, Six Hierarchical Structures, Coefficient of Variation Lower Bound, and Discretization Plateau Effect in the k-Regime Linear Switching Model
- A priori bounds for the generalized parabolic Anderson model in the full subcritical regime
- Bounds on Treewidth via Excluding Disjoint Unions of Cycles
BibTeX
@misc{im2026goodmantype,
title = {{Goodman-type lower bounds for odd cycles I: The dense regime}},
author = {Seonghyuk Im and Taeyoung Kim and Hongseok Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18277},
eprint = {2610.18277},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18277},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Goodman-type lower bounds for odd cycles I: The dense regime
AU - Seonghyuk Im
AU - Taeyoung Kim
AU - Hongseok Yang
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18277
UR - https://arxiv.org/abs/2610.18277
AB - Goodman proved a lower bound on triangle counts which, in graphon language, states that every graphon of edge density p has triangle density at least 2p^2−p. Bennett, Dudek, Lidický, and Pikhurko established the corresponding bound for C_5, determining its minimum density at every Turán density p=1−1/k with an integer k≥3. We extend this bound to every odd cycle in the dense regime: for every odd integer m≥3 and every graphon W with edge density p≥2/3, t(C_m, W) ≥ p^m−p(1−p)^m−1. For 2/3≤ p<1, equality holds precisely for balanced complete k-partite graphons with an integer k≥3, up to graphon equivalence, and we establish qualitative stability at these densities. In the same density range, we also strengthen Kim and Lee's density-sensitive commonality inequality for odd cycles by adding the nonnegative term t(P_m−1,1−W)−(1−p)^m−1 to the lower bound, where P_m−1 is the path with m−1 edges. To prove the main results, we develop a spectral excursion expansion and use Dirichlet averaging to reduce the resulting polynomial inequalities in arbitrarily many spectral variables to a one-variable problem. We prove the one-variable inequality through a uniform inequality comparing odd and even moments of shifted Gamma random variables. We also formalise the odd-cycle lower-bound theorem in Lean 4.
ER -