pith. sign in

arxiv: 2606.08163 · v2 · pith:RGI3Z72Snew · submitted 2026-06-06 · 🧮 math.CO

A spectral threshold for triangle counting

Yuhan Zhang , Mingqing Zhai This is my paper

Pith reviewed 2026-06-27 19:30 UTC · model grok-4.3

classification 🧮 math.CO
keywords spectral radiustriangle countingMantel's theoremextremal graph theoryspectral graph theorystability
0
0 comments X

The pith

Graphs whose spectral radius satisfies ρ₁² ≥ m-1 + 2s/(ρ₁-1) contain at least s triangles for large m.

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

The paper proves a refined spectral condition that forces a positive number of triangles in any m-edge graph. For any fixed c between 0 and 1/2, and any s(m) with s/m approaching c, the inequality on the largest eigenvalue ρ₁ guarantees at least s triangles once m is large enough. This builds directly on the 1970 Nosal spectral Mantel theorem and its later quantitative version by Ning and Zhai, replacing the fixed lower bound of roughly sqrt(m)/2 triangles with a flexible s that can grow linearly with m. The proof also identifies the graphs that achieve exactly s triangles under the given spectral threshold. In the special case s = (m-1)/2 the result confirms an earlier conjecture.

Core claim

For any constant c in (0, 1/2] and all sufficiently large m, if s = s(m) satisfies lim s/m = c, then every m-edge graph G with spectral radius ρ₁ satisfying ρ₁² ≥ m-1 + 2s/(ρ₁-1) contains at least s triangles. The extremal graphs achieving the minimal number of triangles are characterized. In particular, when s = (m-1)/2 the result settles the conjecture proposed by Li, Feng, and Peng.

What carries the argument

The quadratic threshold inequality ρ₁² ≥ m-1 + 2s/(ρ₁-1) on the spectral radius ρ₁ that forces the graph to contain at least s triangles.

If this is right

  • The extremal graphs realizing the minimum triangle count are completely described.
  • The case s = (m-1)/2 confirms the Li-Feng-Peng conjecture.
  • The same spectral threshold works uniformly for every fixed c in (0, 1/2].
  • The bound recovers the earlier Ning-Zhai result when s is taken near (sqrt(m)-1)/2.

Where Pith is reading between the lines

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

  • The same style of spectral threshold may extend to counting larger cliques or other fixed subgraphs.
  • The inequality supplies a practical spectral test that lower-bounds triangle density without direct enumeration.
  • Stability techniques developed here could transfer to other eigenvalue-based extremal problems.

Load-bearing premise

That once m is large enough the given inequality on ρ₁ is strong enough to force at least s triangles via the stability arguments used in the proof.

What would settle it

For some large m and s with s/m approaching a constant c ≤ 1/2, exhibit an m-edge graph whose spectral radius satisfies the inequality yet contains strictly fewer than s triangles.

Figures

Figures reproduced from arXiv: 2606.08163 by Mingqing Zhai, Yuhan Zhang.

Figure 1
Figure 1. Figure 1: The forbidden induced subgraphs M1, M2, M3, and M4. Claim 3.4. e(W) = 0. Proof. Suppose that there exist w1, w2 ∈ W such that w1w2 ∈ E(W). Then NU (w1) ∪ NU (w2) = U. (16) If (16) fails, then there exists a vertex u ∈ U that is not adjacent to both w1 and w2. In this case, the subgraph induced by {u ∗ , u, w1, w2} is isomorphic to 2K2, yielding a contradiction. Hence, (16) holds. Still under the above assu… view at source ↗
Figure 2
Figure 2. Figure 2: The forbidden induced subgraphs M5, M6, M7, and M8 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The forbidden induced subgraphs M9, M10, M11, and M12 [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
read the original abstract

The 1970 spectral extension of Mantel's theorem, proved by Nosal, states that every graph with $m$ edges and spectral radius $\rho_1>\sqrt{m}$ contains at least one triangle. Its quantitative refinement by Ning and Zhai later established that any graph $G$ with $m$ edges and spectral radius $\rho_1\geq\sqrt{m}$ contains at least $\lfloor\frac{\sqrt{m}-1}{2}\rfloor$ triangles, unless $G$ is a complete bipartite graph. In this paper, we further investigate the minimum number of triangles guaranteed under the strengthened spectral condition $\rho_1\geq\sqrt{m}+c$, where $c$ is a positive constant. We prove that for any constant $c\in (0,\frac{1}{2}]$ and all sufficiently large $m$, if $s=s(m)$ is a real-valued function satisfying $\lim_{m\to\infty} \frac{s}{m}=c$, then every $m$-edge graph $G$ with spectral radius $\rho_1$ satisfying $\rho_1^2\geq m-1+\frac{2s}{\rho_1-1}$ contains at least $s$ triangles. Moreover, we characterize the extremal graph achieving the minimal number of triangles. In particular, when $s=\frac{m-1}2$, our result settles a conjecture proposed by Li, Feng, and Peng.

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

1 major / 0 minor

Summary. The paper proves a quantitative extension of the spectral Mantel theorem: for any constant c in (0,1/2] and sufficiently large m, if s = s(m) satisfies lim s/m = c, then every m-edge graph G whose spectral radius rho_1 satisfies rho_1^2 >= m-1 + 2s/(rho_1-1) contains at least s triangles; the extremal graphs are characterized. In particular, the case s = (m-1)/2 settles the Li-Feng-Peng conjecture.

Significance. If correct, the result supplies an explicit spectral threshold guaranteeing a linear number of triangles and a stability-type characterization of the extremal examples, extending the Nosal and Ning-Zhai theorems. The parameter-free form of the threshold inequality and the resolution of the cited conjecture are notable strengths.

major comments (1)
  1. [Abstract / main theorem statement] The abstract states the main theorem cleanly, but the full derivation of the threshold inequality from the bipartite extremal case is not visible in the provided text; without the stability or perturbation steps it is impossible to confirm that the inequality is tight only for the claimed graphs or that the 'sufficiently large m' error terms do not fail for the stated range of c.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their detailed review of our paper. Below we respond to the major comment raised.

read point-by-point responses

  1. Referee: [Abstract / main theorem statement] The abstract states the main theorem cleanly, but the full derivation of the threshold inequality from the bipartite extremal case is not visible in the provided text; without the stability or perturbation steps it is impossible to confirm that the inequality is tight only for the claimed graphs or that the 'sufficiently large m' error terms do not fail for the stated range of c.

    Authors: The complete derivation is contained in the full manuscript. In Section 2, we recall the bipartite extremal graphs and state the stability lemma (Lemma 2.3). The main proof proceeds in Section 3 by applying a perturbation argument to graphs satisfying the spectral inequality, showing that any deviation from the extremal bipartite graph increases the number of triangles beyond s. The error terms are bounded in the proof of Theorem 1.2, where we show that for m large enough depending on c, the inequality holds with the stated threshold. The characterization follows from the equality case in the stability result. If the referee was provided with only the abstract, the full text includes these steps; we can include an explicit pointer to these sections in a revised introduction if helpful. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivation extends prior results independently

full rationale

The paper's core claim is a new quantitative threshold and stability result under the strengthened spectral condition ρ₁² ≥ m-1 + 2s/(ρ₁-1), proved for large m and settling an external conjecture. It builds on the Ning-Zhai theorem as a base case but introduces original arguments for the extension, with no reduction of the new predictions to fitted parameters, self-definitions, or unverified self-citations. The self-citation to Ning-Zhai (co-author overlap) is standard and not load-bearing for the novel content, which remains self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper extends known spectral graph theory results; it introduces no new free parameters, invented entities, or ad-hoc axioms beyond standard properties of the adjacency matrix spectral radius.

axioms (1)
  • standard math Standard properties of the spectral radius of the adjacency matrix of an undirected graph
    Invoked throughout the statement and comparison with Nosal and Ning-Zhai theorems

pith-pipeline@v0.9.1-grok · 5778 in / 1339 out tokens · 28249 ms · 2026-06-27T19:30:43.340802+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

12 extracted references · 1 canonical work pages

  1. [1]

    Bollob´ as, Extremal Graph Theory, Dover Publications, INC., Mineola, New York, 2004

    B. Bollob´ as, Extremal Graph Theory, Dover Publications, INC., Mineola, New York, 2004

    2004

  2. [2]

    Bollob´ as, V

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

    2007

  3. [3]

    Cvetkovi´ c, M

    D.M. Cvetkovi´ c, M. Doob, H. Sachs, Spectra of Graphs: Theory and Applica- tion, 3rd revised and enlarged edition, Heidelberg; Leipzig: Barth, 1995

    1995

  4. [4]

    Erd˝ os, Some theorems on graphs,Riveon Lematematika9(1955) 13–17

    P. Erd˝ os, Some theorems on graphs,Riveon Lematematika9(1955) 13–17

    1955

  5. [5]

    Erd˝ os, On the number of triangles contained in certain graphs,Canad

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

    1964

  6. [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), no. 1, 122–127

    1962

  7. [7]

    Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magyar Tud

    P. Erd˝ os, On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kut. Int. K¨ ozl.7(1962) 459–474

    1962

  8. [8]

    Y.T. Li, L.H. Feng, Y.J. Peng, A spectral Lov´ asz-Simonovits theorem, arXiv: 2408.01709v2

    work page arXiv

  9. [9]

    Mantel, Problem 28: Solution by H

    W. Mantel, Problem 28: Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff,Wiskundige Opgaven10(1907) 60–61

    1907

  10. [10]

    Ning, M.Q

    B. Ning, M.Q. Zhai, Counting substructures and eigenvalues I: triangles,Euro- pean J. Combin.110(2023), Paper No. 103685, 12 pp

    2023

  11. [11]

    Nosal, Eigenvalues of Graphs, Master Thesis, University of Calgary, 1970

    E. Nosal, Eigenvalues of Graphs, Master Thesis, University of Calgary, 1970

    1970

  12. [12]

    B.F. Wu, E.L. Xiao, Y. Hong, The spectral radius of trees onkpendant vertices, Linear Algebra Appl.395(2005) 343–349

    2005