Strong Turán stability (Q5920701): Difference between revisions

Summary: We study maximal \(K_{r+1}\)-free graphs \(G\) of almost extremal size -- typically, \(e(G)=\operatorname{ex}(n,K_{r+1})-O(n)\). We show that any such graph \(G\) must have a large amount of `symmetry': in particular, all but very few vertices of \(G\) must have twins. (Two vertices \(u\) and \(v\) are \textit{twins} if they have the same neighbourhood.) As a corollary, we obtain a new, short proof of a theorem of Simonovits on the structure of extremal \(K_{r+1}\)-free graphs of chromatic number at least \(k\) for all fixed \(k \geq r \geq 2\).