Complete counterexamples to Mubayi's supersaturation conjecture for graphs
Abstract
For a graph F, its extremal number ex(n,F) and extremal graphs denote the maximum number of edges in F-free graphs and the graphs attaining this maximum, respectively. Let hF(n,q) be the minimum number of copies of F in an n-vertex graph with ex(n,F)+q edges, and let tF(n,q) denote the corresponding minimum obtained by adding q edges to an extremal graph. Mubayi (2013) conjectured that for every non-r-partite stable r-uniform hypergraph F with r≥ 2, hF(n,q)≥ q· tF(n,1) holds for all sufficiently large n and all integers q≥ 1. In this paper, we prove that Mubayi's conjecture fails in a stronger sense. For every integer d≥ 2, we construct a family of non-d-partite stable graphs F such that hF(n,q)< q· tF(n,1) for all 1≤ q≤ O(n4/ 3). In particular, these examplesis completely refute Mubayi's conjecture. \noindent\emph{Key words}: extremal graph; supersaturation; chromatic number.
Related
- Strong counterexamples to Mubayi's supersaturation conjecture in every uniformity
- Counterexamples to the Mao-Wu-Xu spectral conjecture and a three-scale boundary for spherical random graphs
- The Keevash--Mubayi simplex-cluster conjecture
- A Complete Proof of the Strong Conjecture about F-Irregular Graphs
- Strict spectral supersaturation for cliques: extremal graphs and sharp thresholds
BibTeX
@misc{zhang2026complete,
title = {{Complete counterexamples to Mubayi's supersaturation conjecture for graphs}},
author = {Liping Zhang and Qinghai Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18876},
eprint = {2610.18876},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18876},
}
RIS
TY - UNPB
TI - Complete counterexamples to Mubayi's supersaturation conjecture for graphs
AU - Liping Zhang
AU - Qinghai Liu
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.18876
UR - https://arxiv.org/abs/2610.18876
AB - For a graph F, its extremal number ex(n,F) and extremal graphs denote the maximum number of edges in F-free graphs and the graphs attaining this maximum, respectively. Let h_F(n,q) be the minimum number of copies of F in an n-vertex graph with ex(n,F)+q edges, and let t_F(n,q) denote the corresponding minimum obtained by adding q edges to an extremal graph. Mubayi (2013) conjectured that for every non-r-partite stable r-uniform hypergraph F with r≥ 2, h_F(n,q)≥ q· t_F(n,1) holds for all sufficiently large n and all integers q≥ 1. In this paper, we prove that Mubayi's conjecture fails in a stronger sense. For every integer d≥ 2, we construct a family of non-d-partite stable graphs F such that h_F(n,q)< q· t_F(n,1) for all 1≤ q≤ O(n^4/ 3). In particular, these examplesis completely refute Mubayi's conjecture. \noindent\emph{Key words}: extremal graph; supersaturation; chromatic number.
ER -