View PDF HTML (experimental)

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 $\varepsilon>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 $\varepsilon 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.

Submission history

From: Hilal Hama Karim [view email]
[v1] Thu, 30 Mar 2023 21:40:04 UTC (14 KB)
[v2] Fri, 28 Aug 2026 12:30:23 UTC (28 KB)