Spectral saturation: inverting the spectral Turán theorem (Q1010943)

Summary: Let \(\mu(G)\) be the \(r\)-partite Turán graph of order \(n\). We prove that if \(G\) is a graph of order \(n\) with \(\mu(G) >\mu (T_{r}(n))\), 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.