Stability for large forbidden subgraphs

✍ Scribed by Vladimir Nikiforov

• Publisher: John Wiley and Sons
• Year: 2009
• Tongue: English
• Weight: 84 KB
• Volume: 62
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.20399

✦ Synopsis

Abstract

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:

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};

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:

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};

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