A general theorem in spectral extremal graph theory

Abstract

The extremal graphs $\mathrm{EX}(n,\mathcal{F})$ and spectral extremal graphs $\mathrm{SPEX}(n,\mathcal{F})$ are the sets of graphs on $n$ vertices with maximum number of edges and maximum spectral radius, respectively, with no subgraph in $\mathcal{F}$. We prove a general theorem which allows us to characterize the spectral extremal graphs for a wide range of forbidden families $\mathcal{F}$ and implies several new and existing results. In particular, whenever $\mathrm{EX}(n,\mathcal{F})$ contains the complete bipartite graph $K_{k,n-k}$ (or certain similar graphs) then $\mathrm{SPEX}(n,\mathcal{F})$ contains the same graph when $n$ is sufficiently large. We prove a similar theorem which relates $\mathrm{SPEX}(n,\mathcal{F})$ and ${\mathrm{SPEX}}_{\hat{I}}\pm (n,\mathcal{F})$, the set of $\mathcal{F}$-free graphs which maximize the spectral radius of the matrix $A_{\hat{I}}\pm =\hat{I}\pm D+(1-\hat{I}\pm )A$, where $A$ is the adjacency matrix and $D$ is the diagonal degree matrix.

This version to appear in Transactions of the AMS