Optimal spectral supersaturation for cliques and odd cycles
Abstract
Let Yn,r,q be the graph obtained from the Turán graph Tn,r by adding q pairwise disjoint edges inside a largest part, and let c(n,F) be the minimum number of copies of F created by adding a single edge to Tn,r. Fang, Li, Lin and Ma proved that for every color-critical graph F with χ(F)=r+1, there exists a constant δF>0 such that for all sufficiently large n and all 1≤ q≤ δF √n, the condition λ(G)≥λ(Yn,r,q) forces at least q c(n,F) copies of F. The bound q=O(√n ) is tight up to a constant factor, in contrast to the linear order n of the edge setting of Mubayi, Pikhurko and Yilma, but the exact constant δF remained unknown for any F. In this paper, building on a structural result of Fang, Li, Lin and Ma, we determine the threshold δF when F is a clique and an odd cycle. For every r≥2, we denote δr :=(1−1/r)√2 and prove that for every ε>0, if n is sufficiently large and 1≤ q≤(δr−ε)√n, then every n-vertex graph G with λ(G)≥λ(Yn,r,q) contains at least q c(n,Kr+1) copies of Kr+1, and δr is best possible. For odd cycles, the threshold is 1/√2. For every k≥1 and ε>0, if n is sufficiently large and 1≤ q≤(1/√2−ε)√n, then every n-vertex graph G with λ(G)≥λ(Yn,2,q) contains at least q c(n,C2k+1) copies of C2k+1, and 1/√2 is best possible. Our results determine both the exact count of copies and the optimal range of q. The behavior in the spectral setting differs from the classical edge setting, in which the range of q is of order n and the threshold is 1/r for cliques by Lovász and Simonovits, and 1/2 for odd cycles by Pikhurko and Yilma.
Related
- Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds
- Sharp edge-spectral supersaturation for odd cycles
- Supersaturation: Cliques and Positive Square Energy
- Spectral and edge conditions for negative Hamiltonian cycles in unbalanced signed graphs
- Spectral extremal hypergraphs without long Berge cycles
BibTeX
@misc{chen2026optimal,
title = {{Optimal spectral supersaturation for cliques and odd cycles}},
author = {Hongzhang Chen and Yongtao Li},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.06038},
eprint = {2610.06038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.06038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal spectral supersaturation for cliques and odd cycles
AU - Hongzhang Chen
AU - Yongtao Li
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.06038
UR - https://arxiv.org/abs/2610.06038
AB - Let Y_n,r,q be the graph obtained from the Turán graph T_n,r by adding q pairwise disjoint edges inside a largest part, and let c(n,F) be the minimum number of copies of F created by adding a single edge to T_n,r. Fang, Li, Lin and Ma proved that for every color-critical graph F with χ(F)=r+1, there exists a constant δ_F>0 such that for all sufficiently large n and all 1≤ q≤ δ_F √n, the condition λ(G)≥λ(Y_n,r,q) forces at least q c(n,F) copies of F. The bound q=O(√n ) is tight up to a constant factor, in contrast to the linear order n of the edge setting of Mubayi, Pikhurko and Yilma, but the exact constant δ_F remained unknown for any F. In this paper, building on a structural result of Fang, Li, Lin and Ma, we determine the threshold δ_F when F is a clique and an odd cycle. For every r≥2, we denote δ_r :=(1−1/r)√2 and prove that for every ε>0, if n is sufficiently large and 1≤ q≤(δ_r−ε)√n, then every n-vertex graph G with λ(G)≥λ(Y_n,r,q) contains at least q c(n,K_r+1) copies of K_r+1, and δ_r is best possible. For odd cycles, the threshold is 1/√2. For every k≥1 and ε>0, if n is sufficiently large and 1≤ q≤(1/√2−ε)√n, then every n-vertex graph G with λ(G)≥λ(Y_n,2,q) contains at least q c(n,C_2k+1) copies of C_2k+1, and 1/√2 is best possible. Our results determine both the exact count of copies and the optimal range of q. The behavior in the spectral setting differs from the classical edge setting, in which the range of q is of order n and the threshold is 1/r for cliques by Lovász and Simonovits, and 1/2 for odd cycles by Pikhurko and Yilma.
ER -