Goodman-type lower bounds for odd cycles I: The dense regime

Source 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 $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\ge3$. We extend this bound to every odd cycle in the dense regime: for every odd integer $m\ge3$ and every graphon $W$ with edge density $p\ge2/3$, $t(C_m, W) \ge p^m-p(1-p)^{m-1}.$ For $2/3\le p<1$, equality holds precisely for balanced complete $k$-partite graphons with an integer $k\ge3$, 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.