Exact stability for Turán's Theorem

Abstract

Turán's Theorem says that an extremal $K_{r+1}$-free graph is $r$-partite. The Stability Theorem of Erdős and Simonovits shows that if a $K_{r+1}$-free graph with $n$ vertices has close to the maximal $t_r(n)$ edges, then it is close to being $r$-partite. In this paper we determine exactly the $K_{r+1}$-free graphs with at least $m$ edges that are farthest from being $r$-partite, for any $m\ge t_r(n)-\hat{I}{´}_r{n}^2$. This extends work by Erdős, Győri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidický and Pfender.

17 pages, 2 figures