A spectral stability theorem for large forbidden graphs

2007/11/22 by Vladimir Nikiforov, Nikiforov, Vladimir
Computer Science · Mathematics · #Advanced Graph Theory Research #Graph theory and applications #Limits and Structures in Graph Theory #math.CO #msc:05C35 #msc:05C50

paper · pdf · doi:10.48550/arxiv.0711.3485

arxiv created 2007/11/22 · arxiv updated 2009/12/01

Abstract

We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and second, our extremal condition is on the spectral radius of the host graph.

Related

• Stability for large forbidden subgraphs
• New proofs of stability theorems on spectral graph problems
• Some new results in extremal graph theory
• An edge-spectral Erdős-Stone-Simonovits theorem and its stability
• Spectral saturation: inverting the spectral Turan theorem