The spectral Erd\H{o}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\'{a}s and Erd\H{o}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\neq T_{n,2}$ with $\lambda(G)\ge\lambda(T_{n,2})$ satisfies \[ \mathrm{bk}(G)\ge\max\Big\{\frac13\lambda(G),\,\lambda(G)-\frac n3,\,2\lambda(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 n3$, 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\{\lambda(G)-\frac{2m}{3\lambda(G)},\,2\lambda(G)-\frac{2m}{\lambda(G)}\Big\}, \] which strengthens the bound $\mathrm{bk}(G)\ge\frac13\lambda(G)$ of Zhao, You, Zeng and Zhang. As an application of our method, we prove a triangle counting bound $t(G)\ge\frac13(\lambda(G)+1)(\lambda(G)^2-m)$, which improves the result of Bollob\'{a}s and Nikiforov [J. Combin. Theory Ser B. (2007)]. Finally, we prove stability results at both thresholds: if $\lambda(G)\ge(\frac12-o(1))n$, then either $\mathrm{bk}(G)\ge(\frac16-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(\frac13-o(1))\sqrt m$ or $G$ differs from a complete bipartite graph in $o(m)$ edges.