The spectral Erdős book theorem: sharp bounds and stability
Abstract
The booksize 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(Tn,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 λ(G)>λ(Tn,2), where λ(G) is the spectral radius of the adjacency matrix. We answer this question in a strong form: every n-vertex graph G≠ Tn,2 with λ(G)≥λ(Tn,2) satisfies bk(G)≥max{1/3λ(G), λ(G)−n/3, 2λ(G)−n}. Consequently, the condition λ(G)>λ(Tn,2) forces bk(G)≥⌊ n/6⌋+1. The middle term is a spectral improvement of Edwards' bound bk(G)≥2m/n−n/3, and all three bounds are best possible. These results come from the edge-spectral setting: every graph G with m edges and λ(G)≥√m that is not a complete bipartite graph satisfies bk(G)≥max{λ(G)−2m/3λ(G), 2λ(G)−2m/λ(G)}, which strengthens the bound bk(G)≥1/3λ(G) of Zhao, You, Zeng and Zhang. As an application of our method, we prove a triangle counting bound t(G)≥1/3(λ(G)+1)(λ(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 λ(G)≥(1/2−o(1))n, then either bk(G)≥(1/6−o(1))n or G can be made into Tn,2 by adding and deleting o(n2) edges; if λ(G)≥(1−o(1))√m, then either bk(G)≥(1/3−o(1))√m or G differs from a complete bipartite graph in o(m) edges.
Related
- Sharp bounds for Duke--Erdős--Rödl problems on cycle-connected subgraphs
- Sharp bounds in Ionescu--Wainger multiplier theorem for canonical fractions
- A sharp spectral multiplier theorem on the Engel group
- A sharp stability inequality of Liouville's theorem for quasiregular mappings on bounded domains
- A Sharp Spectral Mantel Theorem for Quantum Transport
BibTeX
@misc{li2026spectral,
title = {{The spectral Erdős book theorem: sharp bounds and stability}},
author = {Yongtao Li and Lele Liu and Bo Ning},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20225},
eprint = {2609.20225},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20225},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The spectral Erdős book theorem: sharp bounds and stability
AU - Yongtao Li
AU - Lele Liu
AU - Bo Ning
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.20225
UR - https://arxiv.org/abs/2609.20225
AB - The booksize 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 λ(G)>λ(T_n,2), where λ(G) is the spectral radius of the adjacency matrix. We answer this question in a strong form: every n-vertex graph G≠ T_n,2 with λ(G)≥λ(T_n,2) satisfies bk(G)≥max{1/3λ(G), λ(G)−n/3, 2λ(G)−n}. Consequently, the condition λ(G)>λ(T_n,2) forces bk(G)≥⌊ n/6⌋+1. The middle term is a spectral improvement of Edwards' bound bk(G)≥2m/n−n/3, and all three bounds are best possible. These results come from the edge-spectral setting: every graph G with m edges and λ(G)≥√m that is not a complete bipartite graph satisfies bk(G)≥max{λ(G)−2m/3λ(G), 2λ(G)−2m/λ(G)}, which strengthens the bound bk(G)≥1/3λ(G) of Zhao, You, Zeng and Zhang. As an application of our method, we prove a triangle counting bound t(G)≥1/3(λ(G)+1)(λ(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 λ(G)≥(1/2−o(1))n, then either bk(G)≥(1/6−o(1))n or G can be made into T_n,2 by adding and deleting o(n^2) edges; if λ(G)≥(1−o(1))√m, then either bk(G)≥(1/3−o(1))√m or G differs from a complete bipartite graph in o(m) edges.
ER -