A Vertex-Linear Threshold for Eventually Turán good and the Cluster Method
Abstract
A graph H is Kr+1-Turán-good if, for every sufficiently large n, the Turán graph Tr(n) maximizes the number of copies of H among all n-vertex Kr+1-free graphs, and it is strictly Kr+1-Turán-good when this extremal graph is unique. Morrison, Nir, Norin, Rzążewski and Wesolek proved that for every graph H with at least one edge, when r≥ 300v(H)9, H is Kr+1-Turán-good. They asked whether the above bound could be reduced to quadratic order in v(H). In this paper, we answer their question affirmatively, and give a stronger result. We prove that there is an absolute constant C>0 such that every graph H with at least one edge is strictly Kr+1-Turán-good whenever r≥ Cv(H). Our proof uses a substantially different cluster method based on polymer models. Besides proving the vertex-linear Turán-good threshold, this method appears to have further applications. As one illustration, we prove that for every graph H with at least one edge, the normalized chromatic polynomial PH(x)/xv(H) is strictly increasing for every real x≥ CΔ(H), which strengthens the previously best result where x≥ CΔ(H)3/2. This proves a conjecture of Fadnavis.
Related
- Approximating Distributions on Vertex Degrees in Random Hypergraphs via Stein's Method
- Linear circumference in vertex-transitive graphs
- A Unified Linear Programming Approach for Maximizing Vertex-Degree-Based Indices of Trees
- Linear Independence of Random Boolean Tensor Powers at the Dimension Threshold
- When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
BibTeX
@misc{zhao2026vertexlinear,
title = {{A Vertex-Linear Threshold for Eventually Turán good and the Cluster Method}},
author = {Xiamiao Zhao and Liying Kang and Yuanpei Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25038},
eprint = {2609.25038},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25038},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Vertex-Linear Threshold for Eventually Turán good and the Cluster Method
AU - Xiamiao Zhao
AU - Liying Kang
AU - Yuanpei Wang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.25038
UR - https://arxiv.org/abs/2609.25038
AB - A graph H is K_r+1-Turán-good if, for every sufficiently large n, the Turán graph T_r(n) maximizes the number of copies of H among all n-vertex K_r+1-free graphs, and it is strictly K_r+1-Turán-good when this extremal graph is unique. Morrison, Nir, Norin, Rzążewski and Wesolek proved that for every graph H with at least one edge, when r≥ 300v(H)^9, H is K_r+1-Turán-good. They asked whether the above bound could be reduced to quadratic order in v(H). In this paper, we answer their question affirmatively, and give a stronger result. We prove that there is an absolute constant C>0 such that every graph H with at least one edge is strictly K_r+1-Turán-good whenever r≥ Cv(H). Our proof uses a substantially different cluster method based on polymer models. Besides proving the vertex-linear Turán-good threshold, this method appears to have further applications. As one illustration, we prove that for every graph H with at least one edge, the normalized chromatic polynomial P_H(x)/x^v(H) is strictly increasing for every real x≥ CΔ(H), which strengthens the previously best result where x≥ CΔ(H)^3/2. This proves a conjecture of Fadnavis.
ER -