A Vertex-Linear Threshold for Eventually Tur\'an good and the Cluster Method

Abstract

A graph $H$ is $K_{r+1}$-Tur\'an-good if, for every sufficiently large $n$, the Tur\'an 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\'an-good when this extremal graph is unique. Morrison, Nir, Norin, Rz\k{a}\.zewski 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\'an-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\'an-good whenever $r\ge Cv(H)$. Our proof uses a substantially different cluster method based on polymer models. Besides proving the vertex-linear Tur\'an-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.