A Vertex-Linear Threshold for Eventually Turán good and the Cluster Method

Abstract

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\ge 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\ge 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\ge C\Delta (H)$, which strengthens the previously best result where $x\ge C\Delta (H{)}^{3/2}$. This proves a conjecture of Fadnavis.