Eventually Tur\'an good I: Edge-Linear Thresholds and Monotonicity

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. It is strictly $K_{r+1}$-Tur\'an-good if $T_r(n)$ is the unique extremal graph. Morrison, Nir, Norin, Rz\k{a}\.zewski and Wesolek [\emph{JCTB}, 2023] proved that every graph $H$ is $K_{r+1}$-Tur\'an-good whenever $r\ge 300v(H)^9$. They raised the following two questions: 1.Can the sufficient condition $r\ge 300v(H)^9$ be reduced to a condition of quadratic order in $v(H)$? 2.Is the Tur\'an-good property monotone in $r$? More precisely, if a graph $H$ is $K_r$-Tur\'an-good, must it also be $K_{r+1}$-Tur\'an-good? We affirmatively resolve the first question and derive an even stronger bound linear in the edge number: every graph $H$ with at least one edge is strictly $K_{r+1}$-Tur\'an-good and $K_{r+1}$-Tur\'an-stable whenever $r\ge 168e(H)$. This condition is quadratic in $v(H)$ for arbitrary graphs and linear in $v(H)$ for every sparse graph family with $e(H)=O(v(H))$. We answer the second question negatively. For every $r\ge3$, there exists a graph that is strictly $K_r$-Tur\'an-good but not $K_{r+1}$-Tur\'an-good. More quantitatively, for every sufficiently large $h$, there exists a graph $H$ with $v(H)\le h$ and an integer $r=h-2\sqrt h+O(1)$ such that $H$ is strictly $K_r$-Tur\'an-good but not $K_{r+1}$-Tur\'an-good. The monotonicity threshold $\lambda(H)$ is the least integer $R\ge 2$ such that, for every $r\ge R$, the graph $H$ is $K_{r+1}$-Tur\'an-good whenever it is $K_r$-Tur\'an-good. For \[ \lambda_{\max}(h)=\max\{\lambda(H)\mid v(H)\le h\}, \] our two results yield \[ h-2\sqrt h-O(1)\le \lambda_{\max}(h)\le 84h^2. \]