Spectral Saturation: Inverting the Spectral Turán Theorem

Abstract

Let $\mu\left( G\right) $ be the largest eigenvalue of a graph $G$ and $T_{r}\left( n\right) $ be the $r$-partite Turán graph of order $n.$

We prove that if $G$ is a graph of order $n$ with $\mu\left( G\right)>\mu\left( T_{r}\left( n\right) \right)$, then $G$ contains various large supergraphs of the complete graph of order $r+1,$ e.g., the complete $r$-partite graph with all parts of size $\log n$ with an edge added to the first part.

We also give corresponding stability results.