Supersaturation thresholds for expanded color-critical graphs
Abstract
For a k-uniform hypergraph L, let hL(n,q) be the minimum number of copies of L in an n-vertex k-graph with ex(n,L)+q edges. Let tL(n,q) be the minimum number of copies obtained by adding q edges to an extremal L-free k-graph. A graph is color-critical if deleting a suitable edge decreases its chromatic number. Let 𝒦k(F) be the expanded graph obtained by adding k−2 new vertices to each edge of F, with disjoint sets of new vertices for distinct edges. Mubayi proved that, for every clique Kr with r≥4 and fixed $ q>0$, $ h_{\mathcal K_3(K_r)}(n,q)\ge qt_{\mathcal K_3(K_r)}(n,1)$ for every sufficiently large n. Pikhurko and Yilma later proved that, for every color-critical graph F, there is a constant εF>0 such that hF(n,q)=tF(n,q) for every sufficiently large n and 1≤ q≤εF n. We extend this equality to expanded color-critical graphs. Let d>k≥3. For every color-critical graph F with χ(F)=d+1, there is a constant ε>0 such that $ h_{\mathcal K_k(F)}(n,q)=t_{\mathcal K_k(F)}(n,q)$ for every sufficiently large n and 1≤ q≤εnk−1. Let qL(n) be the largest integer q such that hL(n,s)=tL(n,s) for every integer 1≤ s≤ q. We give a sufficient condition for qL(n)=ΘL(nk−1) and an explicit family satisfying it. We also give a different sufficient condition under which qL(n)=ΩL(nk−1/2) and an explicit family satisfying it. \noindent \emph{Keywords.} Supersaturation; extremal graph; color-critical graph; chromatic number; expanded graph; hypergraph.
Related
- Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds
- Optimal detection of geometry in random graphs and kernel matrices at critical thresholds
- Unbalanced spectral Turán problem for color-critical graphs with prescribed large maximum degree
- A solution to a conjecture on the signless Laplacian spectral radius for t-color-critical graphs
- Complete counterexamples to Mubayi's supersaturation conjecture for graphs
BibTeX
@misc{zhang2026supersaturation,
title = {{Supersaturation thresholds for expanded color-critical graphs}},
author = {Liping Zhang and Qinghai Liu and Yanmei Hong and Wang Xi and Jinze Hu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.15348},
eprint = {2610.15348},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.15348},
}
RIS
TY - UNPB
TI - Supersaturation thresholds for expanded color-critical graphs
AU - Liping Zhang
AU - Qinghai Liu
AU - Yanmei Hong
AU - Wang Xi
AU - Jinze Hu
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.15348
UR - https://arxiv.org/abs/2610.15348
AB - For a k-uniform hypergraph L, let h_L(n,q) be the minimum number of copies of L in an n-vertex k-graph with ex(n,L)+q edges. Let t_L(n,q) be the minimum number of copies obtained by adding q edges to an extremal L-free k-graph. A graph is color-critical if deleting a suitable edge decreases its chromatic number. Let 𝒦_k(F) be the expanded graph obtained by adding k−2 new vertices to each edge of F, with disjoint sets of new vertices for distinct edges. Mubayi proved that, for every clique K_r with r≥4 and fixed $ q>0$, $ h_{\mathcal K_3(K_r)}(n,q)\ge qt_{\mathcal K_3(K_r)}(n,1)$ for every sufficiently large n. Pikhurko and Yilma later proved that, for every color-critical graph F, there is a constant ε_F>0 such that h_F(n,q)=t_F(n,q) for every sufficiently large n and 1≤ q≤ε_F n. We extend this equality to expanded color-critical graphs. Let d>k≥3. For every color-critical graph F with χ(F)=d+1, there is a constant ε>0 such that $ h_{\mathcal K_k(F)}(n,q)=t_{\mathcal K_k(F)}(n,q)$ for every sufficiently large n and 1≤ q≤εn^k−1. Let q_L(n) be the largest integer q such that h_L(n,s)=t_L(n,s) for every integer 1≤ s≤ q. We give a sufficient condition for q_L(n)=Θ_L(n^k−1) and an explicit family satisfying it. We also give a different sufficient condition under which q_L(n)=Ω_L(n^k−1/2) and an explicit family satisfying it. \noindent \emph{Keywords.} Supersaturation; extremal graph; color-critical graph; chromatic number; expanded graph; hypergraph.
ER -