On a spectral booksize problem fo non bipartite graphs

Benju Wang; Jinlong Shu; ZhenZhen Lou

REVIEW 1 major objections 3 minor 24 references

On a spectral booksize problem fo non bipartite graphs

T0 review · 1 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper proves that the optimal asymptotic constant for spectral booksize lower bounds is 1/4.

desk verdict Sharp 1/4 constant for the spectral booksize problem, with an intricate proof that leans on an unverified black-box classification theorem; worth a careful referee. read the letter →

arxiv 2608.05947 v1 pith:LVLC554P submitted 2026-08-06 math.CO

Benju Wang , Zhenzhen Lou , Jinlong Shu This is my paper · ORCID

classification math.CO MSC 05C5005C35

keywords booksizespectralradiusnon-bipartitegraphextremaltheoryproblemexceptionalfamilymatrixperturbationprincipaleigenvector

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper answers an asymptotic question about books in graphs whose spectral radius sits just below the threshold $\sqrt{m}$. It proves that for every $\varepsilon>0$, all sufficiently large $m$-edge non-bipartite graphs without isolated vertices satisfying $\rho(G)^2 \ge m-1+\frac{2}{\rho(G)-1}$ either belong to the explicit family $S^+_{m,s}$ (a complete bipartite graph with one extra edge inside the larger part) or have booksize greater than $(\frac14-\varepsilon)\sqrt{m}$. A companion construction yields infinitely many non-exceptional graphs with the same spectral condition and booksize below $C_0\sqrt{m}$ for every $C_0>\frac14$, so the constant $\frac14$ cannot be improved asymptotically. Together with earlier results at and above the threshold, this fixes $\frac14$ as the best possible asymptotic constant in the problem.

What carries the argument

The load-bearing mechanism is a partition of the vertex set coming from a vertex of maximum principal eigenvector coordinate, together with the identity relating the spectral defect $m-\rho(G)^2$ to the eigenvector-weighted excess of internal edges and the missing cross-edges. A local inequality derived from the principal eigenvector shows that, when the booksize is small, only a bounded number of edges lie inside the two parts. The cross-adjacency matrix is then compared with the all-one matrix through a low-rank approximation theorem and an identity for sums of squared two-by-two minors, yielding that the graph differs from a complete bipartite graph in a bounded number of edges. In the branch where the maximum eigenvector coordinate is small, a perturbation argument forces exactly one internal edge and a rank-one cross matrix, giving $G\cong S^+_{m,s}$; in the other branch, proximity to the complete bipartite graph $K_{S,T}$ lets the external classification theorem identify $G$ as $S^+_{m,s}$. Thus $S^+_{m,s}$—the complete bipartite graph $K_{s,(m-1)/s}$ with one added edge inside the part of order $(m-1)/s$—is the unique asymptotic obstruction.

What would settle it

For some $\varepsilon>0$, find arbitrarily large $m$ and an $m$-edge non-bipartite graph without isolated vertices that satisfies $\rho(G)^2\ge m-1+\frac{2}{\rho(G)-1}$, is not isomorphic to any $S^+_{m,s}$, and has $\operatorname{bk}(G)\le(\frac14-\varepsilon)\sqrt{m}$. Theorem 1.4 asserts that no such infinite family exists, so one counterexample at arbitrarily large $m$ settles the claim negatively. Independent verification of the external classification theorem for all parameters with $m\ge(240r)^2$ would check the only black-box assumption.

Watch

Extended reading notes

Core claim

The central claim of the paper is that $\frac14$ is the asymptotically optimal constant in the spectral booksize problem below the No\-sal threshold. Theorem 1.4 states: for every $0<\varepsilon<\frac14$, there is an $m_0(\varepsilon)$ such that any $m$-edge non-bipartite graph $G$ without isolated vertices with $m\ge m_0(\varepsilon)$ and $\rho(G)^2 \ge m-1+\frac{2}{\rho(G)-1}$ is either isomorphic to $S^+_{m,s}$ for some admissible divisor $s\mid m-1$, or has $\operatorname{bk}(G)>(\frac14-\varepsilon)\sqrt{m}$. Proposition 4.1 constructs infinitely many non-exceptional graphs satisfying the same spectral hypothesis with $\operatorname{bk}(G)<C_0\sqrt{m}$ for every $C_0>\frac14$. The two statements together show that $\frac14$ is the best possible asymptotic constant.

Load-bearing premise

The proof's final classification of the large-coordinate branch depends on an external theorem stating that a non-bipartite graph with many edges and no large book must have spectral radius below the assumed threshold unless it is one of the exceptional graphs; if that theorem is false or has a hidden range restriction, the conclusion fails.

Editorial extensions

If this is right

For all sufficiently large $m$, the best possible constant in the problem is asymptotically $\frac14$, improving the earlier $\frac1{240}$ and tightening the then-known upper bound $\frac13$.
Any sufficiently large non-bipartite graph without isolated vertices that satisfies the spectral condition and is not one of the $S^+_{m,s}$ graphs must contain a book of size at least $(\frac14-o(1))\sqrt{m}$.
The proof gives a structural shadow: under the spectral condition with small booksize, the graph is at bounded distance from a complete bipartite graph, with only a bounded number of internal edges.
In the range $\rho(G)^2\ge m$, the earlier sharp theorem already gives $\operatorname{bk}(G)\ge \rho(G)/3$, so the new contribution is precisely the sub-threshold window $m-1+\frac{2}{\rho(G)-1}\le \rho(G)^2<m$.
The construction in Proposition 4.1 shows the barrier is real: graphs obtained from $K_{s,t}$ by adding a path of length two inside one part satisfy the spectral condition with booksize asymptotic to $\sqrt{m}/\sqrt{\alpha}$ for any $\alpha\in(4,16)$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The bounded-distance-from-complete-bipartite structure probably extends to a stability theorem: graphs in the sub-threshold window that avoid $S^+_{m,s}$ should be close to complete bipartite plus one small book, with a quantitative gap between $\operatorname{bk}(G)$ and $\frac14\sqrt{m}$ governed by the distance.
The same low-rank matrix machinery may transfer to spectral extremal problems for other fixed subgraphs, where an all-one rectangle approximation would again be the natural extremal template.
One could test whether the threshold term $\frac{2}{\rho(G)-1}$ is an artifact: replacing it by any $o(1)$ term may leave the asymptotic constant $\frac14$ unchanged, in which case the phenomenon is purely a sub-threshold spectral phenomenon.
Because the last branch relies on an external classification as a black box, a direct computational verification of that classification for moderate values of the book parameter would independently test the only non-elementary step.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Zhai, Li, and Lou's 1/240 bound is now sharp: the paper proves the optimal asymptotic constant is 1/4. This is not a routine tightening. The proof has two genuinely new ingredients: a matrix approximation argument using Eckart–Young–Mirsky and Cauchy–Binet to show the cross-adjacency matrix is nearly an all-one rectangle, and a Perron-vector perturbation dichotomy that splits the argument into two branches. The sharpness construction, with t chosen near α s, is also new and gives infinitely many non-exceptional graphs showing that no constant larger than 1/4 can hold. The main theorem is cleanly stated, and the reduction to the case ρ^2 < m via the earlier sharp result of Zhao, You, Zeng, and Zhang is sensible.

The proof is intricate and, as far as I can check, internally coherent. The identity (2), the bounded-defect reduction, the matrix lemmas, and the two Perron-coordinate branches all line up. I did not find a genuine gap. The soft spots are two. First, the μ > M/√ρ branch of Lemma 3.12 rests entirely on Theorem 1.3 of [22] as a black box. That theorem is published and cited, but it shares an author with this paper, so the current work does not independently verify that classification; if [22, Theorem 1.3] has a hidden restriction, the proof of Theorem 1.4 collapses. I don't consider that a reason to reject, but a referee should check that theorem's statement carefully. Second, Section 4 has reciprocal-limit typos: γ_{s,t} should converge to 4/√α, not 4√α, and the two displayed inequalities that follow have the same reciprocal slip. The surrounding algebra makes the intended content obvious, and the conditions α>4 and α<16 work out exactly, so these are minor. One more small thing: the paper says 'Since G is non-bipartite, we have ρ≥2'; that is false (odd cycles can have spectral radius below 2), but it is harmless because in the strict range m > ρ^2 the spectral condition forces ρ > 3.

Who gets value: spectral extremal graph theorists, and anyone tracking booksize problems or Erdős-type spectral conjectures. The paper deserves a serious referee. My own verdict is acceptance after the reciprocal typos are fixed; the black-box dependency should be flagged in the review but is not disqualifying.

Referee Report

1 major / 3 minor

Summary. The paper determines the asymptotically optimal constant in a spectral booksize problem of Zhai, Li, and Lou. For every epsilon in (0,1/4) and all sufficiently large m, the main theorem (Theorem 1.4) shows that every m-edge non-bipartite graph without isolated vertices satisfying rho(G)^2 >= m-1+2/(rho(G)-1) either is one of the explicit graphs S+_{m,s} or has booksize bk(G) > (1/4-epsilon) sqrt(m). The proof uses a Perron-vector identity, a bounded-defect reduction, Eckart-Young and Cauchy-Binet matrix estimates, and a final case distinction on the maximum Perron coordinate. Section 4 supplies infinitely many non-exceptional graphs satisfying the same spectral condition with bk(G) < C0 sqrt(m) for every C0 > 1/4, showing that the constant 1/4 cannot be improved.

Significance. If correct, the result resolves the asymptotic form of Question 1.1 and improves the previously known constant 1/240 to the optimal 1/4. The main proof is unusually transparent for a problem of this type: the local identity (2), the Phi-estimate of Lemma 3.1, the bounded-defect reduction of Corollary 3.1, and the matrix-approximation steps in Lemmas 3.5 and 3.6 are internally consistent, and the sharpness construction in Proposition 4.1 is explicit and self-contained. The main caveat is that the mu > M/sqrt(rho) branch of Lemma 3.12 delegates the final classification to Theorem 1.3 of [22]; since that theorem is quoted in full and its hypotheses are verified, this is a scope limitation rather than a gap. The reciprocal-limit typo in Section 4 is local and does not affect the conclusion.

major comments (1)

[Section 3, Lemma 3.12] The last paragraph of Lemma 3.12 closes the mu > M/sqrt(rho) branch by invoking Theorem 1.3 of [22]. I verified the hypotheses: the graph is non-bipartite, m > rho^2 > (240 b_r)^2, and G is B_{b_r+1}-free, with the r=0 case handled by taking b_r=1. The step is therefore logically valid, but the main theorem in that branch is exactly as strong as [22, Theorem 1.3]. Because that external theorem has overlapping authorship and is not reproved here, the introduction should state explicitly that Theorem 1.4 inherits the classification from [22].

minor comments (3)

[Section 4, Proposition 4.1] The displayed limit for gamma_{s,t} is incorrect: gamma_{s,t} tends to 4/sqrt(alpha), not 4 sqrt(alpha). The two subsequent displayed limits, m - rho^2 -> 2 - 4 sqrt(alpha) and rho^2 - (m-1+2/(rho-1)) -> 4 sqrt(alpha) - 1, should be 2 - 4/sqrt(alpha) and 4/sqrt(alpha) - 1. The inequalities used in the proof remain valid because alpha > 4 and alpha < 16.
[Section 3, proof of Theorem 1.4] The heading 'Proof of Theorem 1.4 (i)' is spurious, since Theorem 1.4 has no displayed subparts; it should simply read 'Proof of Theorem 1.4'.
[Section 3, Corollary 3.1] The bound r/rho <= 1/4 - epsilon/2 is derived under the contrary assumption r <= (1/4 - epsilon) sqrt(m); making that dependence explicit in the sentence would improve readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proof is self-contained except for an independent published classification theorem [22] used as a black box in one branch.

full rationale

The paper's derivation chain does not define its objects in terms of the conclusion, fit parameters to the target data, or smuggle in the answer via a self-citation. The main lower-bound proof develops independent identities (Eq. (2), Lemmas 3.1-3.3) and internal matrix lemmas (Lemmas 3.5-3.8). The partition argument bounds the number of internal edges and then classifies both Perron-vector branches. In the mu > M/sqrt(rho) branch, Lemma 3.12 derives r < rho/240 and applies Theorem 1.3 of Zhai, Li, and Lou [22] to conclude G is isomorphic to S+_{m,s}. That theorem is a cited, already-published classification result with explicit hypotheses (m >= (240r)^2, B_{r+1}-free) that are verified inside the proof; its conclusion is the S+ family, not the lower bound bk(G) > (1/4-eps)sqrt(m), so it does not assume the target result. Although [22] shares coauthor Lou with the present paper, the citation is real evidence under the stated rules: it is parameter-free and its assumptions do not include the present theorem. The sharpness construction in Proposition 4.1 is self-contained and computes rho and bk directly; no fitted value is relabeled as a prediction. No circular step was found.

Assumptions & free parameters 1 free parameters · 6 assumptions · 0 invented entities

No data are fitted and no new physical or mathematical entities are introduced. The central theorem depends on standard matrix analysis facts and on two published external theorems. The only overlapping-authorship dependency is Theorem 1.3 of Zhai, Li, and Lou, which is used as a black box in one branch; the rest of the proof is self-contained. The alpha parameter in the sharpness construction is listed for completeness but is not fitted to any data.

free parameters (1)

alpha in Proposition 4.1 = chosen in (max{4, C0^-2}, 16), not fitted to data
The sharpness construction uses t = floor(alpha s) and the asymptotic ratio bk(G)/sqrt(m) tends to 1/sqrt(alpha). No data are fitted, and the lower-bound theorem does not depend on alpha; it is a construction parameter in the optimality argument.

assumptions (6)

standard math Perron-Frobenius theorem for connected graphs (Lemma 2.1)
Used to guarantee a positive Perron vector and simple largest eigenvalue throughout the proof.
standard math Eckart-Young-Mirsky theorem (Lemma 2.2)
Used to approximate the cross-adjacency matrix by a rank-one matrix and to control the squared Frobenius distance by the tail sum of squared singular values.
standard math Cauchy-Binet identity for 2x2 minors (Lemma 2.3)
Used in Lemma 3.6 to connect the number of nonzero 2x2 minors of a 0-1 matrix to its singular values.
standard math Weyl eigenvalue perturbation inequality
Used in Lemmas 3.7 and 3.8 to bound the shift of the largest eigenvalue under the bounded operator H0.
domain assumption Theorem 1.2 of Zhao, You, Zeng, and Zhang [24]
External result used to handle the range rho^2 >= m, giving bk(G) >= rho/3 > sqrt(m)/3. It is cited and not proved in this paper.
domain assumption Theorem 1.3 of Zhai, Li, and Lou [22]
External spectral extremal theorem used in Lemma 3.12 to force G to be S+_{m,s} in the branch mu > M/sqrt(rho). It is cited and not proved here, and it has overlapping authorship through Lou.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On a spectral booksize problem fo non bipartite graphs." pith.science (2026). https://pith.science/paper/LVLC554P

@misc{pith2026260805947,
  author       = {Pith},
  title        = {Pith review of: On a spectral booksize problem fo non bipartite graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/LVLC554P}},
  note         = {Machine review of arXiv:2608.05947}
}

abstract

The $\text{bk}(G)$ of a graph $G$ is the maximum number of triangles sharing a common edge. Motivated by a classical conjecture of Erd\H{o}s, spectral lower bounds for the booksize have received considerable attention. For a positive divisor $s$ of $m-1$ with $\frac{m-1}{s}\ge2$, let $S_{m,s}^{+}$ be obtained from $K_{s,\frac{m-1}{s}}$ by adding one edge inside the part of order $\frac{m-1}{s}$. Zhai et al. proved that, apart from this explicit family, every $m$-edge non-bipartite graph satisfying $\rho(G)^2\ge m-1+\frac{2}{\rho(G)-1}$ has booksize greater than $\frac{1}{240}\sqrt{m}$, and they asked for the best possible constant. We answer this question asymptotically. For every $0<\varepsilon<\frac{1}{4}$ and all sufficiently large $m$, every $m$-edge non-bipartite graph $G$ without isolated vertices satisfying the same spectral condition either is isomorphic to $S_{m,s}^{+}$ for some such integer $s$, or satisfies $\text{bk}(G)>\left(\frac{1}{4}-\varepsilon\right)\sqrt{m}$. We also give infinitely many graphs outside the exceptional family showing that no constant larger than $\frac{1}{4}$ is possible. Thus $\frac{1}{4}$ is the optimal asymptotic constant in the problem of Zhai et al.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 22 canonical work pages

[22]

M. Zhai, R. Li, Z. Lou, Advances on two spectral conjectures regarding booksize of graphs,European J. Combin.138(2026) 104431

work page 2026
[1]

Bollob´as, V

B. Bollob´as, V . Nikiforov, Books in graphs,European J. Combin.26(2005) 259–270

work page 2005
[2]

H. Chen, Y . Li, Q. Tang, Supersaturation in Nosal graphs: triangles and books, arXiv:2607.16746 (2026). 19

work page Pith review arXiv 2026
[3]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, Books versus triangles at the extremal density,SIAM J. Discrete Math.34(2020) 385–398

work page 2020
[4]

Conlon, J

D. Conlon, J. Fox, Y . Wigderson, Ramsey number of books and quasirandomness, Combinatorica42(2022) 309–363

work page 2022
[5]

Eckart, G

C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika1(1936) 211–218

work page 1936
[6]

Erd ˝os, On a theorem of Rademacher-Tur´an,Illinois J

P. Erd ˝os, On a theorem of Rademacher-Tur´an,Illinois J. Math.6(1962) 122–127

work page 1962
[7]

Erd˝os, R

P. Erd˝os, R. Faudree, E. Gy ¨ori, On the book size of graphs with large minimum degree,Studia Sci. Math. Hungar.30(1995) 25–46

work page 1995

Show all 24 references

[8]

Erd˝os, R

P. Erd˝os, R. Faudree, C. Rousseau, Extremal problems involving vertices and edges on odd cycles,Discrete Math.101(1992) 23–31

1992
[9]

R. A. Horn, C. R. Johnson,Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013

2013
[10]

Khadˇziivanov, V

N. Khadˇziivanov, V . Nikiforov, Solution of a problem of P. Erd˝os about the maximum number of triangles with a common edge in a graph,C. R. Acad. Bulgare Sci.32 (1979) 1315–1318

1979
[11]

Y . Li, L. Feng, Y . Peng, A spectral Erd˝os–Faudree–Rousseau theorem,J. Graph Theory110(2025), no. 4, 408–425

2025
[12]

Y . Li, H. Liu, S. Zhang, An edge-spectral Erd˝os–Stone–Simonovits theorem and its stability, arXiv:2508.15271 (2025)

2025 arXiv
[13]

Y . Li, H. Liu, S. Zhang, More on Nosal’s spectral theorem: books and 4-cycles,J. Combin. Theory Ser. B179(2026) 219–249

2026
[14]

Y . Li, Y . Peng, The maximum spectral radius of non-bipartite graphs forbidding short odd cycles,Electron. J. Combin.29(2022) Paper No. P4.2

2022
[15]

H. Lin, B. Ning, B. Wu, An extension of Nosal’s theorem,Combin. Probab. Comput. 30(2021) 258–270

2021
[16]

R. Liu, L. Miao, Spectral Tur´an problem of non-bipartite graphs: forbidden books, European J. Combin.126(2025) 104136

2025
[17]

Mirsky, Symmetric gauge functions and unitarily invariant norms,Quart

L. Mirsky, Symmetric gauge functions and unitarily invariant norms,Quart. J. Math. Oxford (2)11(1960) 50–59

1960
[18]

Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin

V . Nikiforov, Some inequalities for the largest eigenvalue of a graph,Combin. Probab. Comput.11(2002) 179–189

2002
[19]

Nikiforov, The maximum spectral radius ofC4-free graphs of given order and size, Linear Algebra Appl.430(2009) 2898–2905

V . Nikiforov, The maximum spectral radius ofC4-free graphs of given order and size, Linear Algebra Appl.430(2009) 2898–2905. 20

2009
[20]

Nikiforov, On a theorem of Nosal, arXiv:2104.12171 (2021)

V . Nikiforov, On a theorem of Nosal, arXiv:2104.12171 (2021)

2021 arXiv
[21]

Nosal,Eigenvalues of Graphs, Ph.D

E. Nosal,Eigenvalues of Graphs, Ph.D. thesis, University of Calgary, 1970

1970
[23]

M. Zhai, H. Lin, J. Shu, Spectral extrema of graphs with fixed size: cycles and complete bipartite graphs,European J. Combin.95(2021) 103322

2021
[24]

X. Zhao, L. You, J. Zeng, X. Zhang, Two problems on booksize and triangular edges in Nosal graphs, arXiv:2607.15071 (2026). 21

2026 arXiv

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.

[1] [22]

M. Zhai, R. Li, Z. Lou, Advances on two spectral conjectures regarding booksize of graphs,European J. Combin.138(2026) 104431

work page 2026

[2] [1]

Bollob´as, V

B. Bollob´as, V . Nikiforov, Books in graphs,European J. Combin.26(2005) 259–270

work page 2005

[3] [2]

H. Chen, Y . Li, Q. Tang, Supersaturation in Nosal graphs: triangles and books, arXiv:2607.16746 (2026). 19

work page Pith review arXiv 2026

[4] [3]

Conlon, J

D. Conlon, J. Fox, B. Sudakov, Books versus triangles at the extremal density,SIAM J. Discrete Math.34(2020) 385–398

work page 2020

[5] [4]

Conlon, J

D. Conlon, J. Fox, Y . Wigderson, Ramsey number of books and quasirandomness, Combinatorica42(2022) 309–363

work page 2022

[6] [5]

Eckart, G

C. Eckart, G. Young, The approximation of one matrix by another of lower rank, Psychometrika1(1936) 211–218

work page 1936

[7] [6]

Erd ˝os, On a theorem of Rademacher-Tur´an,Illinois J

P. Erd ˝os, On a theorem of Rademacher-Tur´an,Illinois J. Math.6(1962) 122–127

work page 1962

[8] [7]

Erd˝os, R

P. Erd˝os, R. Faudree, E. Gy ¨ori, On the book size of graphs with large minimum degree,Studia Sci. Math. Hungar.30(1995) 25–46

work page 1995