Every graph is eventually Turán-good and Turán-stable
Abstract
Let Tr(n) denote the complete r-partite graph on n vertices whose part sizes differ by at most one. A graph H is called Kr+1-Turán-good if, for all sufficiently large n, the graph Tr(n) contains the maximum number of copies of H among all n-vertex Kr+1-free graphs. We say that H is Kr+1-Turán-stable if, for every ε>0, there exist δ>0 and n0 such that, whenever n≥ n0 and an n-vertex Kr+1-free graph G contains at least ex(n,H,Kr+1)−δnv(H) copies of H, the edit distance between G and Tr(n) is at most ε n2, where v(H) denotes the order of H. In this paper, we prove that every graph H is both Kr+1-Turán-good and Kr+1-Turán-stable for r≥ 4v(H)3+11v(H)2. This strengthens results of Morrison, Nir, Norin, Rzążewski, and Wesolek~[J. Combin. Theory Ser. B, 2023] and Gerbner and Hama Karim~[J. Graph Theory, 2024], and gives a positive answer to a question of Morrison, Nir, Norin, Rzążewski, and Wesolek. We also prove that inj(H,G)≤ inj(H,Tr(n)) for every n-vertex Kr+1-free graph G and for r≥ 40v(H)3, where inj(H,G) denotes the number of injective homomorphisms from H to G. Finally, we give a negative answer to another question of Morrison, Nir, Norin, Rzążewski, and Wesolek.
Related
- A Vertex-Linear Threshold for Eventually Turán good and the Cluster Method
- Cayley graph diameters for fixed cycle types are eventually quasipolynomial
- A note on the Kővári--Sós--Turán theorem for stable hypergraphs
- The asymptotic stability of the stable solitons of the generalized good Boussinesq equation
- A counterexample to the Fang--Lin conjecture: Edge and spectral extremality diverge near a Turán graph
BibTeX
@misc{yang2026every,
title = {{Every graph is eventually Turán-good and Turán-stable}},
author = {Jiabao Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29493},
eprint = {2609.29493},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29493},
}
RIS
TY - UNPB
TI - Every graph is eventually Turán-good and Turán-stable
AU - Jiabao Yang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.29493
UR - https://arxiv.org/abs/2609.29493
AB - Let T_r(n) denote the complete r-partite graph on n vertices whose part sizes differ by at most one. A graph H is called K_r+1-Turán-good if, for all sufficiently large n, the graph T_r(n) contains the maximum number of copies of H among all n-vertex K_r+1-free graphs. We say that H is K_r+1-Turán-stable if, for every ε>0, there exist δ>0 and n_0 such that, whenever n≥ n_0 and an n-vertex K_r+1-free graph G contains at least ex(n,H,K_r+1)−δn^v(H) copies of H, the edit distance between G and T_r(n) is at most ε n^2, where v(H) denotes the order of H. In this paper, we prove that every graph H is both K_r+1-Turán-good and K_r+1-Turán-stable for r≥ 4v(H)^3+11v(H)^2. This strengthens results of Morrison, Nir, Norin, Rzążewski, and Wesolek~[J. Combin. Theory Ser. B, 2023] and Gerbner and Hama Karim~[J. Graph Theory, 2024], and gives a positive answer to a question of Morrison, Nir, Norin, Rzążewski, and Wesolek. We also prove that inj(H,G)≤ inj(H,T_r(n)) for every n-vertex K_r+1-free graph G and for r≥ 40v(H)^3, where inj(H,G) denotes the number of injective homomorphisms from H to G. Finally, we give a negative answer to another question of Morrison, Nir, Norin, Rzążewski, and Wesolek.
ER -