Аннотация:
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 talk we determine exactly the K_{r+1}-free graphs with at least m edges that are farthest from being r-partite, for any m > t_r(n) - δn^2.
This extends work by Erdős, Győri and Simonovits, and proves a conjecture of Balogh, Clemen, Lavrov, Lidický and Pfender. Joint work with Alexander Roberts and Alex Scott.