Stability for large forbidden subgraphs

In this note we strengthen the stability theorem of Erdős and Simonovits. Write K r ( s 1 , …, s r ) for the complete r ‐partite graph with classes of sizes s 1 , …, s r and T r ( n ) for the r ‐partite Turán graph of order n . Our main result is: For all r ≥2 and all sufficiently small c >0, ε>0, every graph G of sufficiently large order n with e ( G )>(1−1/ r −ε) n 2 /2 satisfies one of the conditions: (a) G contains a \documentclass{article} \usepackage{amssymb}\footskip=0pc\pagestyle{empty} \begin{document} $K_{r+1} (\lfloor c\,\mbox{ln}\,n \rfloor,\ldots,\lfloor c\,\mbox{ln}\,n \rfloor,\lceil n^{{1}-\sqrt{c}}\rceil)$ \end{document} ; (b) G differs from T r ( n ) in fewer than (ε 1/3 + c 1/(3 r +3) ) n 2 edges.Letting µ( G ) be the spectral radius of G , we prove also a spectral stability theorem: For all r ≥2 and all sufficiently small c >0, ε>0, every graph G of sufficiently large order n with µ( G )>(1−1/ r −ε) n satisfies one of the conditions: (a) G contains a \documentclass{article} \usepackage{amssymb}\footskip=0pc\pagestyle{empty} \begin{document} $K_{r+1}(\lfloor c\,\mbox{ln}\,n\rfloor,\ldots,\lfloor c\,\mbox{ln}\,n\rfloor,\lceil n^{1-\sqrt{c}}\rceil)$ \end{document} ; (b) G differs from T r ( n ) in fewer than (ε 1/4 + c 1/(8r+8) ) n 2 edges. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 362–368, 2009