Stability from graph symmetrization arguments in generalized Turán problems

Abstract

Given graphs $H$ and $F$, $\mathrm{ex}(n,H,F)$ denotes the largest number of copies of $H$ in $F$-free $n$-vertex graphs. Let $\chi (H)<\chi (F)=r+1$. We say that $H$ is $F$-Turán-stable if the following holds. For any $\epsilon >0$ there exists $\delta >0$ such that if an $n$-vertex $F$-free graph $G$ contains at least $\mathrm{ex}(n,H,F)-\delta n^{|V(H)|}$ copies of $H$, then the edit distance of $G$ and the $r$-partite Turán graph is at most $\epsilon n^2$. We say that $H$ is weakly $F$-Turán-stable if the same holds with the Turán graph replaced by any complete $r$-partite graph $T$. It is known that such stability implies exact results in several cases. We show that complete multipartite graphs with chromatic number at most $r$ are weakly $K_{r+1}$-Turán-stable. Answering a question of Morrison, Nir, Norin, Rzażewski and Wesolek positively, we show that for every graph $H$, if $r$ is large enough, then $H$ is $K_{r+1}$-Turán-stable. Finally, we prove that if $H$ is bipartite, then it is weakly $C_{2k+1}$-Turán-stable for $k$ large enough.

We would like to thank Casey Tompkins and Dömötör Pálvölgyi for pointing out some mistakes in the previous version that was published the in Journal of Graph Theory (107(4),681-892, 2024). Those mistakes are fixed in this current version. Particularly, the proof of Theorem 1.1 and the definition of $F^{\ast }$ in Section 4 have been revised

References in corpus (1)

• Every graph is eventually Turán-good