2025/08/21 by Yongtao Li, Hong Liu, Li, Yongtao +3 · 2 citations
Mathematics · #Limits and Structures in Graph Theory #Graph theory and applications #Spectral Theory in Mathematical Physics
paper · pdf · doi:10.48550/arxiv.2508.15271
We study the extremal problem that relates the spectral radius λ(G) of an F-free graph G with its number of edges. Firstly, we prove that for any graph F with chromatic number χ(F)=r+1≥ 3, if G is an F-free graph on m edges, then λ2(G)≤ (1-(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 λ2(G)=(1- (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≥ 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 λ(G)>√(m), then there exist two vertices in G that have at least (1)/(2)√(m) - O(1) common neighbors. This bound is the best possible as witnessed by a random construction.