Metraipolis › archive › dc_ba657c2716ed

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20225
License (as archived)
CC0-1.0
Archived
2026-10-10T04:47:15.038Z
SHA-256 of the archived text
d0b4c165f764903af10353c84dc8587c0e91c646e023620da4c7f163130e8fce
Stable URL of this page
https://metraipolis.com/documento/dc_ba657c2716ed

How to cite

The spectral Erdős book theorem: sharp bounds and stability — arXiv:2609.20225 — arXiv (en), https://arxiv.org/abs/2609.20225 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_ba657c2716ed (Metraipolis archive dc_ba657c2716ed, sha256 d0b4c165f764903af10353c84dc8587c0e91c646e023620da4c7f163130e8fce)
BibTeX
@misc{dcba657c2716ed,
  title = {The spectral Erdős book theorem: sharp bounds and stability — arXiv:2609.20225},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20225},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_ba657c2716ed; sha256 d0b4c165f764903af10353c84dc8587c0e91c646e023620da4c7f163130e8fce},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20225. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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\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á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.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.20225 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:15:33.141Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).