The spectral Erdős book theorem: sharp bounds and stability

Abstract

The booksize $\mathrm{bk}(G)$ of a graph $G$ is the largest number of triangles sharing a common edge. A classical theorem of Edwards, conjectured by Bollobás and Erdős, states that every $n$-vertex graph $G$ with $e(G)>e(T_{n,2})$ has booksize greater than $n/6$. Zhai and Lin [J. Graph Theory 102 (2023) 502--520] asked whether the same conclusion holds under the spectral condition $\lambda (G)>\lambda (T_{n,2})$, where $\lambda (G)$ is the spectral radius of the adjacency matrix. We answer this question in a strong form: every $n$-vertex graph $G\ne T_{n,2}$ with $\lambda (G)\ge \lambda (T_{n,2})$ satisfies \[ \mathrm{bk}(G)\ge\max\Big\{\frac13λ(G),\,λ(G)-\frac n3,\,2λ(G)-n\Big\}. \] Consequently, the condition $\lambda (G)>\lambda (T_{n,2})$ forces $\mathrm{bk}(G)\ge \lfloor n/6\rfloor +1$. The middle term is a spectral improvement of Edwards' bound $\mathrm{bk}(G)\ge \frac{2m}{n}-\frac{n}{3}$, and all three bounds are best possible. These results come from the edge-spectral setting: every graph $G$ with $m$ edges and $\lambda (G)\ge \sqrt{m}$ that is not a complete bipartite graph satisfies \[ \mathrm{bk}(G)\ge\max\Big\{λ(G)-\frac{2m}{3λ(G)},\,2λ(G)-\frac{2m}{λ(G)}\Big\}, \] which strengthens the bound $\mathrm{bk}(G)\ge \frac{1}{3}\lambda (G)$ of Zhao, You, Zeng and Zhang. As an application of our method, we prove a triangle counting bound $t(G)\ge \frac{1}{3}(\lambda (G)+1)(\lambda (G{)}^2-m)$, which improves the result of Bollobás and Nikiforov [J. Combin. Theory Ser B. (2007)]. Finally, we prove stability results at both thresholds: if $\lambda (G)\ge (\frac{1}{2}-o(1))n$, then either $\mathrm{bk}(G)\ge (\frac{1}{6}-o(1))n$ or $G$ can be made into $T_{n,2}$ by adding and deleting $o(n^2)$ edges; if $\lambda (G)\ge (1-o(1))\sqrt{m}$, then either $\mathrm{bk}(G)\ge (\frac{1}{3}-o(1))\sqrt{m}$ or $G$ differs from a complete bipartite graph in $o(m)$ edges.

arXiv comment28 pages. We add a new author and add many new results