The cycle of length four is strictly $F$-Turán-good

Abstract

Given an $(r+1)$-chromatic graph $F$ and a graph $H$ that does not contain $F$ as a subgraph, we say that $H$ is strictly $F$-Turán-good if the Turán graph $T_r(n)$ is the unique graph containing the maximum number of copies of $H$ among all $F$-free graphs on $n$ vertices for every $n$ large enough. Győri, Pach and Simonovits (1991) proved that cycle $C_4$ of length four is strictly $K_{r+1}$-Turán-good for all $r\ge 2$. In this article, we extend this result and show that $C_4$ is strictly $F$-Turán-good, where $F$ is an $(r+1)$-chromatic graph with $r\ge 2$ and a color-critical edge. Moreover, we show that every $n$-vertex $C_4$-free graph $G$ with $N(H,G)=\ex(n,C_4,F)-o(n^4)$ can be obtained by adding or deleting $o(n^2)$ edges from $T_r(n)$. Our proof uses the flag algebra method developed by Razborov (2007).

16 pages