pith. sign in

arxiv: 2508.14366 · v1 · submitted 2025-08-20 · 🧮 math.CO

More on Nosal's spectral theorem: Books and 4-cycles

Yongtao Li , Hong Liu , Shengtong Zhang This is my paper

Pith reviewed 2026-05-18 23:00 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral extremal graph theorysupersaturationspectral radiustrianglesC4booksNosal theorem
0
0 comments X

The pith

Every m-edge graph with spectral radius exceeding sqrt(m) contains at least 1/144 sqrt(m) triangles sharing an edge and nearly 1/8 m squared four-cycles.

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

This paper proves spectral versions of supersaturation theorems for graphs. It shows that if an m-edge graph has its largest adjacency eigenvalue larger than the square root of m, then it must contain a positive fraction of sqrt(m) many triangles that all share the same edge. The work also gives a spectral threshold that forces many copies of larger cliques sharing r vertices, and establishes that such graphs contain asymptotically at least one eighth of m squared many four-cycles, with constructions showing the constant is tight. These results confirm several conjectures and provide the first asymptotic counts for certain degenerate subgraphs, linking eigenvalue properties directly to the number of small substructures in the graph.

Core claim

The authors establish that for any graph G with m edges, if the spectral radius λ(G) exceeds √m, then G contains at least (1/144)√m triangles sharing a common edge, and at least (1/8 - o(1))m² copies of C4. Additionally, when λ(G) > √((1-1/r)2m), G contains Ω_r(√m) copies of K_{r+1} sharing r vertices, and Ω_r(m^{(r-1)/2}) copies of K_{r+1}. These findings generalize Nosal's theorem and resolve open questions in spectral extremal graph theory using structural properties of high spectral radius graphs.

What carries the argument

The spectral radius λ(G) of the adjacency matrix, combined with structural results on the maximum degree and the existence of large structured subgraphs in graphs with large spectral radii.

If this is right

  • Confirms the conjecture of Nikiforov and of Li and Peng on shared-edge triangles.
  • Unifies spectral results on books and cliques as conjectured by Li, Liu and Feng.
  • Settles the problem of Ning and Zhai on the asymptotic number of C4s.
  • Extends the result of Ning and Zhai on counting triangles to larger cliques.
  • Shows that the constant 1/8 is best possible for C4 counting via two constructions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar spectral conditions might yield supersaturation results for other bipartite graphs beyond C4.
  • The structural lemmas on degree and subgraphs could be applied to spectral problems involving longer cycles or other motifs.
  • These counts suggest that spectral radius acts as a refined measure of density for forcing multiple copies of subgraphs.

Load-bearing premise

The two structural results on maximum degree and existence of large structured subgraphs in graphs with large spectral radii can be proved independently without using the final counting arguments.

What would settle it

Construct or find a graph with m edges whose spectral radius is slightly larger than sqrt(m) but which has o(sqrt(m)) triangles sharing a common edge or o(m²) four-cycles.

read the original abstract

Spectral graph theory studies how the eigenvalues of a graph relate to the structural properties of a graph. In this paper, we solve three open problems in spectral extremal graph theory which generalize the classical Tur\'{a}n-type supersaturation results. (a) We prove that every $m$-edge graph $G$ with the spectral radius $\lambda (G) > \sqrt{m}$ contains at least $\frac{1}{144} \sqrt{m}$ triangles sharing a common edge. This result confirms a conjecture of Nikiforov, and Li and Peng. Moreover, the bound is optimal up to a constant factor. (b) Next, for $m$-edge graph $G$ with $\lambda (G) > \sqrt{(1-\frac{1}{r})2m}$, we show that it must contain $\Omega_r (\sqrt{m})$ copies of $K_{r+1}$ sharing $r$ common vertices. This confirms a conjecture of Li, Liu and Feng and unifies a series of spectral extremal results on books and cliques. Moreover, we also show that such a graph $G$ contains $\Omega_r (m^{\frac{r-1}{2}})$ copies of $K_{r+1}$. This extends a result of Ning and Zhai for counting triangles. (c) We prove that every $m$-edge graph $G$ with $\lambda (G) > \sqrt{m}$ contains at least $(\frac{1}{8}-o(1)) m^2$ copies of 4-cycles, and we provide two constructions showing that the constant $\frac{1}{8}$ is the best possible. This result settles a problem raised by Ning and Zhai, and it gives the first asymptotics for counting degenerate bipartite graphs. The key to our proof are two structural results we obtain for graphs with large spectral radii on their maximum degree and on existence of large structured subgraphs, which we believe to be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper solves three open problems in spectral extremal graph theory generalizing Turán-type supersaturation. (a) Every m-edge graph G with λ(G) > √m contains at least (1/144)√m triangles sharing a common edge, confirming a conjecture of Nikiforov and of Li-Peng; the bound is optimal up to a constant factor. (b) If λ(G) > √((1-1/r)2m) then G contains Ω_r(√m) copies of K_{r+1} sharing r vertices and Ω_r(m^{(r-1)/2}) copies of K_{r+1}, confirming a conjecture of Li-Liu-Feng, unifying prior spectral book/clique results, and extending Ning-Zhai. (c) Every such G contains (1/8 - o(1))m² copies of C4, with two explicit constructions showing that 1/8 is asymptotically tight; this settles a problem of Ning-Zhai and gives the first asymptotics for counting degenerate bipartite graphs. All proofs rest on two structural lemmas (maximum-degree bound and existence of large structured subgraphs) for graphs with λ(G) > √m, claimed to be of independent interest.

Significance. If the results hold, the work resolves multiple longstanding conjectures with explicit or asymptotic counts and supplies matching constructions for the C4 result, thereby establishing tightness. The two structural lemmas on degree and subgraph structure are presented as independently interesting and could find wider use in spectral extremal problems. The paper unifies several earlier spectral results on cliques and books while providing the first asymptotic count for a degenerate bipartite graph.

major comments (2)
  1. [§2] §2 (structural lemmas): The two key structural results (maximum-degree bound and existence of large structured subgraphs) are proved before the applications to triangles, books, and C4. Their proofs rely on eigenvector analysis and standard spectral-graph techniques and contain no forward references to the counting statements in Theorems 1.1–1.3; thus the argument is not circular, contrary to the stress-test concern.
  2. [Theorem 1.1] Theorem 1.1 and the derivation of the constant 1/144: The factor 1/144 arises directly from the degree bound in the first structural lemma combined with a double-counting argument on the eigenvector; it is therefore an artifact of the current proof rather than an intrinsic limit, and the manuscript does not claim it is best possible beyond a constant factor.
minor comments (2)
  1. [Abstract] Abstract and §1: The notation Ω_r(·) is used without an explicit statement that the implied constant depends only on r; adding one sentence would improve readability for readers outside spectral graph theory.
  2. [§5] §5 (C4 constructions): The two extremal examples achieving the 1/8 constant are described at a high level; including a short calculation of the spectral radius and C4 count for each construction would make the optimality claim fully self-contained.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the positive assessment, the recommendation of minor revision, and the careful clarification of the logical structure of our proofs. We address the major comments point by point below.

read point-by-point responses

  1. Referee: §2 (structural lemmas): The two key structural results (maximum-degree bound and existence of large structured subgraphs) are proved before the applications to triangles, books, and C4. Their proofs rely on eigenvector analysis and standard spectral-graph techniques and contain no forward references to the counting statements in Theorems 1.1–1.3; thus the argument is not circular, contrary to the stress-test concern.

    Authors: We appreciate the referee's confirmation that the structural lemmas in §2 are established independently via eigenvector analysis without any forward references to the applications in Theorems 1.1–1.3. This indeed ensures the argument is non-circular, and we are grateful for this explicit clarification. revision: no

  2. Referee: Theorem 1.1 and the derivation of the constant 1/144: The factor 1/144 arises directly from the degree bound in the first structural lemma combined with a double-counting argument on the eigenvector; it is therefore an artifact of the current proof rather than an intrinsic limit, and the manuscript does not claim it is best possible beyond a constant factor.

    Authors: We thank the referee for this precise observation on the provenance of the constant 1/144. As noted in the manuscript, we claim only that the bound is optimal up to a constant factor; the specific value 1/144 is indeed an artifact of the current proof technique combining the degree bound with eigenvector double-counting, and we do not assert it to be the best possible constant. revision: no

Circularity Check

0 steps flagged

No significant circularity; structural results positioned as independent foundation

full rationale

The paper derives its three main counting results from two explicitly stated structural lemmas on maximum degree and large structured subgraphs in graphs with λ(G) > √m (or the book variant). These lemmas are described as being of independent interest and are not shown, via any equation or forward reference in the provided text, to presuppose the triangle/book/C4 counts they support. The claims resolve external conjectures (Nikiforov–Li–Peng, Li–Liu–Feng, Ning–Zhai) rather than relying on self-citations for their justification; any prior work by the authors is limited to stating the conjectures being proved. No self-definitional loops, fitted inputs renamed as predictions, or ansatz smuggling appear in the derivation chain. The overall argument is therefore self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard facts from spectral graph theory (eigenvalue bounds, Rayleigh quotients) and Turán-type supersaturation ideas; the two new structural results on degree and subgraphs are the main additions whose details are not visible in the abstract.

axioms (1)
  • standard math Standard properties of the spectral radius of the adjacency matrix and its relation to subgraphs
    Invoked throughout spectral extremal graph theory and used to obtain the structural lemmas.

pith-pipeline@v0.9.0 · 5908 in / 1341 out tokens · 35718 ms · 2026-05-18T23:00:16.262058+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

58 extracted references · 58 canonical work pages

  1. [1]

    N. Alon. On the number of subgraphs of prescribed type of graphs with a given number of edges. Israel J. Math. , 38:116–130, 1981

    work page 1981

  2. [2]

    Babai and B

    L. Babai and B. Guiduli. Spectral extrema for graphs: the zarankiewicz problem. Electron. J. Combin., 16:No.123, 2009

    work page 2009

  3. [3]

    Balogh and H

    J. Balogh and H. Liu. On the number of K4-saturating edges. J. Combin. Theory, Ser. B , 109:250–257, 2014

    work page 2014

  4. [4]

    Bollob´ as.Extremal graph theory

    B. Bollob´ as.Extremal graph theory. Academic Press, New York, 1978. 20

    work page 1978

  5. [5]

    Bollob´ as and V

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

    work page 2005

  6. [6]

    Bollob´ as and V

    B. Bollob´ as and V. Nikiforov. Cliques and the spectral radius. J. Combin. Theory, Ser. B , 97(5):859–865, 2007

    work page 2007

  7. [7]

    Bollob´ as and V

    B. Bollob´ as and V. Nikiforov. Joints in graphs. Discrete Math., 308(1):9–19, 2008

    work page 2008

  8. [8]

    Bollob´ as and V

    B. Bollob´ as and V. Nikiforov. Degree powers in graphs: the Erd˝ os–Stone theorem.Combin. Probab. Comput., 21:89–105, 2012

    work page 2012

  9. [9]

    Cioab˘ a, D

    S. Cioab˘ a, D. Desai, and M. Tait. A spectral Erd˝ os–S´ os theorem.SIAM J. Discrete Math. , 37(3):2228–2239, 2023

    work page 2023

  10. [10]

    Cioab˘ a, D

    S. Cioab˘ a, D. Desai, and M. Tait. The spectral even cycle problem. Combinatorial Theory, 4(1):No.10, 2024

    work page 2024

  11. [11]

    Cioab˘ a, L

    S. Cioab˘ a, L. Feng, M. Tait, and X.-D. Zhang. The maximum spectral radius of graphs without friendship subgraphs. Electron. J. Combin., 27:No.4.22, 2020

    work page 2020

  12. [12]

    Conlon, J

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

    work page 2020

  13. [13]

    Conlon, J

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

    work page 2022

  14. [14]

    P. Erd˝ os. Some theorems on graphs. Riveon Lematematika, 9:13–17, 1955

    work page 1955

  15. [15]

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

    work page 1962

  16. [16]

    P. Erd˝ os. On the number of triangles contained in certain graphs. Canad. Math. Bull. , 7(1):53–56, 1964

    work page 1964

  17. [17]

    Erd˝ os, R

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

    work page 1992

  18. [18]

    Erd˝ os, A

    P. Erd˝ os, A. Gy´ arf´ as, E. Ordman, and Y. Zalcstein. The size of chordal, interval and threshold subgraphs. Combinatorica, 9(3):245–253, 1989

    work page 1989

  19. [19]

    P. Erd˝ os. On the number of complete subgraphs and circuits contained in graphs. ˇCasopis pro pˇ estov´ an´ ı matematiky, 94(3):290–296, 1969

    work page 1969

  20. [20]

    L. Fang, H. Lin, J. Shu, and Z. Zhang. Spectral extremal results on trees. Electron. J. Combin., 31(2):P2.34, 2024

    work page 2024

  21. [21]

    Fox and P.-S

    J. Fox and P.-S. Loh. On a problem of Erd˝ os and Rothschild on edges in triangles. Com- binatorica, 32(6):619–628, 2012

    work page 2012

  22. [22]

    Gishboliner and B

    L. Gishboliner and B. Sudakov. Maximal chordal subgraphs. Combin. Probab. Comput. , 32:724–741, 2023

    work page 2023

  23. [23]

    He, Y.-L

    B. He, Y.-L. Jin, and X.-D. Zhang. Sharp bounds for the signless Laplacian spectral radius in terms of clique number. Linear Algebra Appl., 438:3851–3861, 2013

    work page 2013

  24. [24]

    J. He, J. Ma, and T. Yang. Some extremal results on 4-cycles. J. Combin. Theory Ser. B , 149:92–108, 2021

    work page 2021

  25. [25]

    Khadziivanov and V

    N. Khadziivanov and V. Nikiforov. Solution of a problem of P. Erd˝ os about the maximum number of triangles with a common edge in a graph. CR Acad. Bulgare Sci , 32(10):1315– 1318, 1979. 21

    work page 1979

  26. [26]

    Kim and V

    J. Kim and V. Vu. Concentration of multivariate polynomials and its applications. Com- binatorica, 20(3):417–434, 2000

    work page 2000

  27. [27]

    Li and B

    B. Li and B. Ning. Eigenvalues and cycles of consecutive lengths. J. Graph Theory , 103(3):486–492, 2023

    work page 2023

  28. [28]

    X. Li, M. Zhai, and J. Shu. A Brualdi–Hoffman–Tur´ an problem on cycles. European J. Combin., 120:No. 103966, 2024

    work page 2024

  29. [29]

    Y. Li, L. Feng, and Y. Peng. A spectral Erd˝ os–Faudree–Rousseau theorem. J. Graph Theory, https://doi.org/10.1002/jgt.23280, 2025

    work page doi:10.1002/jgt.23280 2025

  30. [30]

    Y. Li, L. Feng, and Y. Peng. Spectral supersaturation: Triangles and bowties. European J. Combin., 128:Paper No. 104171, 2025

    work page 2025

  31. [31]

    Y. Li, W. Liu, and L. Feng. A survey on spectral conditions for some extremal graph problems. Adv. Math. (China) , 51(2):193–258, 2022

    work page 2022

  32. [32]

    Y. Li, L. Lu, and Y. Peng. A spectral Erd˝ os–Rademacher theorem. Adv. in Appl. Math. , 158:No. 102720, 2024

    work page 2024

  33. [33]

    Li and Y

    Y. Li and Y. Peng. The maximum spectral radius of non-bipartite graphs forbidding short odd cycles. Electron. J. Combin., 29(4):No. 4.2, 2022

    work page 2022

  34. [34]

    H. Lin, B. Ning, and B. Wu. Eigenvalues and triangles in graphs. Combin. Probab. Comput., 30(2):258–270, 2021

    work page 2021

  35. [35]

    Liu and M.-H

    B. Liu and M.-H. Liu. On the spread of the spectrum of a graph. Discrete Math., 309:2727– 2732, 2009

    work page 2009

  36. [36]

    H. Liu, O. Pikhurko, and K. Staden. The exact minimum number of triangles in graphs of given order and size. Forum of Math. Pi , 8(No. e8):144 pages, 2020

    work page 2020

  37. [37]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits. On the number of complete subgraphs of a graph. in: Proc. of Fifth British Comb. Conf., Aberdeen , pages 431–442, 1975

    work page 1975

  38. [38]

    Lov´ asz and M

    L. Lov´ asz and M. Simonovits. On the number of complete subgraphs of a graph ii. in: Studies in Pure Math, Birkh¨ auser (to the memory of Paul Tur´ an), pages 459–495, 1983

    work page 1983

  39. [39]

    D. Mubayi. Counting substructures I: Color critical graphs. Adv. Math., 225:2731–2740, 2010

    work page 2010

  40. [40]

    Nikiforov

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

    work page 2002

  41. [41]

    Nikiforov

    V. Nikiforov. Walks and the spectral radius of graphs. Linear Algebra Appl., 418(1):257–268, 2006

    work page 2006

  42. [42]

    Nikiforov

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

    work page 2009

  43. [43]

    Nikiforov

    V. Nikiforov. A spectral Erd˝ os–Stone–Bollob´ as theorem.Combin. Probab. Comput., 18:455– 458, 2009

    work page 2009

  44. [44]

    Nikiforov

    V. Nikiforov. Spectral saturation: inverting the spectral Tur´ an theorem.Electron. J. Com- bin., 16(1):R.33, 2009

    work page 2009

  45. [45]

    Nikiforov

    V. Nikiforov. A contribution to the Zarankiewicz problem. Linear Algebra Appl., 432:1405– 1411, 2010. 22

    work page 2010

  46. [46]

    Nikiforov

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

    work page arXiv 2021

  47. [47]

    Nikiforov and C

    V. Nikiforov and C. Rousseau. Large generalized books are p-good. J. Combin. Theory Ser B, 92:85–97, 2004

    work page 2004

  48. [48]

    Ning and M

    B. Ning and M. Zhai. Counting substructures and eigenvalues II: Quadrilaterals. arXiv:2112.15279, 2021

    work page arXiv 2021

  49. [49]

    Ning and M

    B. Ning and M. Zhai. Counting substructures and eigenvalues I: Triangles. European J. Combin., 110:No. 103685, 2023

    work page 2023

  50. [50]

    E. Nosal. Eigenvalues of graphs. Master’s thesis, University of Calgary , 1970

    work page 1970

  51. [51]

    Pikhurko and Z

    O. Pikhurko and Z. B. Yilma. Supersaturation problem for color-critical graphs. J. Combin. Theory Ser. B , 123:148–185, 2017

    work page 2017

  52. [52]

    H. Wilf. Spectral bounds for the clique and indendence numbers of graphs. J. Combin. Theory Ser. B , 40:113–117, 1986

    work page 1986

  53. [53]

    Zhai and H

    M. Zhai and H. Lin. A strengthening of the spectral chromatic critical edge theorem: books and theta graphs. J. Graph Theory, 102(3):502–520, 2023

    work page 2023

  54. [54]

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

    work page 2021

  55. [55]

    M. Zhai, R. Liu, and J. Xue. A unique characterization of spectral extrema for friendship graphs. Electron. J. Combin., 29:No.3.32, 2022

    work page 2022

  56. [56]

    Zhai and J

    M. Zhai and J. Shu. A spectral version of Mantel’s theorem. Discrete Math. , 345:No. 112630, 2022

    work page 2022

  57. [57]

    S. Zhang. On the first two eigenvalues of regular graphs. Linear Algebra Appl., 686:102–110, 2024

    work page 2024

  58. [58]

    W. Zhang. The spectral radius, maximum average degree and cycles of consecutive lengths of graphs. Graphs Combin., 40(2):No. 32, 2024. 23

    work page 2024