An edge-spectral Erdős-Stone-Simonovits theorem and its stability

Abstract

We study the extremal problem that relates the spectral radius $\lambda (G)$ of an $F$-free graph $G$ with its number of edges. Firstly, we prove that for any graph $F$ with chromatic number $\chi (F)=r+1\ge 3$, if $G$ is an $F$-free graph on $m$ edges, then ${\lambda }^2(G)\le (1-\frac{1}{r}+o(1))2m$. This provides a unified extension of both the Erdős--Stone--Simonovits theorem and its vertex-spectral version due to Nikiforov, and confirms a conjecture proposed by Li, Liu and Feng. We also establish the corresponding edge-spectral stability, showing that if $G$ is an $F$-free graph on $m$ edges with ${\lambda }^2(G)=(1-\frac{1}{r}-o(1))2m$, then $G$ differs from a complete bipartite graph by $o(m)$ edges when $r=2$, and $G$ differs from an $r$-partite Turán graph by $o(m)$ edges when $r\ge 3$. This extends the classical Erdős--Simonovits stability theorem. As an application of our method, we improve a result of Zhai, Lin and Shu by showing that if $\lambda (G)>\sqrt{m}$, then there exist two vertices in $G$ that have at least $\frac{1}{2}\sqrt{m}-O(1)$ common neighbors. This bound is the best possible as witnessed by a random construction.

30 pages. Any suggestions are welcome