Pith. sign in

REVIEW 2 major objections 5 minor 26 references

Edge-spectral supersaturation for tripartite color-critical graphs

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read The paper proves that crossing the split-graph spectral threshold forces optimal polynomial many copies of tripartite color-critical graphs $K^+_{s,t}$ and odd cycles.

desk verdict New and likely correct polynomial-order supersaturation bounds for two chi=3 families, but the proof leans on an unverified same-team stability lemma that should be reproduced before publication. read the letter →

arxiv 2608.04485 v2 pith:V52JACE5 submitted 2026-08-05 math.CO

Longfei Fang , Huiqiu Lin , Mingqing Zhai This is my paper · ORCID
classification math.CO MSC 05C5005C35
keywords edge-spectralsupersaturationspectralradiuscolor-criticalgraphtripartiteoddcyclesplitK_{st}^+Turanthreshold
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

Edge-spectral extremal graph theory asks what happens when a graph's spectral radius exceeds the largest value allowed while avoiding a prescribed subgraph. This paper proves that for two families of three-chromatic color-critical graphs, crossing the exact split-graph threshold forces not just one forbidden copy but polynomially many. For $K^+_{s,t}$ with $t+1\ge s\ge 3$, every sufficiently large $m$-edge graph with $\rho(G)>g_{s-1}(m)$ contains $\Omega(m^{(s+t-1)/2})$ copies. For odd cycles, $\rho(G)>g_k(m)$ forces $\Omega(m^k)$ copies of $C_{2k+1}$. Both exponents are tight up to constant factors, so the paper turns earlier edge-spectral existence theorems into supersaturation theorems in the harder three-chromatic setting.

What carries the argument

The central object is the spectral threshold $g_r(m):=\frac{r-1+\sqrt{4m-r^2+1}}{2}$, which is the spectral radius of the split graph $S_{r,m}$ (a clique of size $r$ joined to a large independent set, with one extra vertex fixing the residue class). The argument assumes a graph $G$ with $\rho(G)>g_{s-1}(m)$ and too few copies, extracts an $\varepsilon$-core subgraph $H$ (no dense subgraphs), and uses the quoted stability lemma to conclude $H$ is $\varepsilon$-close to a complete bipartite graph $K_{U_1,U_2}$. From then on the Perron eigenvector and the minimal distance partition $(U_1,U_2)$ carry the counting: internal edges inside $U_1$ or $U_2$ are shown to generate many copies of $K^+_{s,t}$ via common neighborhoods, and every other configuration is ruled out by comparing the spectral radius of a modified graph with $g_{s-1}(h)$. The sharpness construction uses a $4s$-regular $C_4$-free graph joined to an independent set.

What would settle it

A direct way to refute Theorem 1.5 would be to produce, for arbitrarily large $m$ and any fixed constant $c>0$, an $m$-edge graph with $\rho(G)>g_{s-1}(m)$ but fewer than $c m^{(s+t-1)/2}$ copies of $K^+_{s,t}$; no such graph can exist if the theorem is correct. A more targeted check is to test Lemma 2.2 independently by searching for a graph with $\rho(G)\approx\sqrt{m}$, $o(m^{f/2})$ copies of a three-chromatic $F$, and edit distance $\Omega(m)$ from every complete bipartite graph.

Watch

Extended reading notes

Core claim

The central claim is that the spectral threshold $g_r(m)$ is a genuine supersaturation threshold for these color-critical graphs. Theorem 1.5 states that whenever $t+1\ge s\ge3$ and $G$ has $m$ edges with $\rho(G)>g_{s-1}(m)$, then $N(K^+_{s,t},G)=\Omega(m^{(s+t-1)/2})$; Theorem 1.6 gives $N(C_{2k+1},G)=\Omega(m^k)$ under $\rho(G)>g_k(m)$ for every $k\ge2$. The paper also constructs graphs showing that neither lower bound can be raised by more than a constant factor. In short, exceeding the threshold that rules out a single copy automatically forces the best possible polynomial surplus of copies.

Load-bearing premise

The proof depends on a cited stability lemma (Lemma 2.2 from the authors' previous paper [4]), not proved here, which says that a three-chromatic graph with few forbidden copies and spectral radius near $\sqrt{m}$ must be nearly bipartite; if that lemma fails, the reduction of a counterexample to a near-bipartite core collapses.

Editorial extensions

If this is right

  • Corollary 1.7 extends the odd-cycle result to every graph $F$ with $C_{2k+1}\subseteq F\subseteq K^+_{k+1,k}$, giving $N(F,G)=\Omega(m^k)$ under the same spectral condition, again tight up to constants.
  • The exponents $\frac{s+t-1}{2}$ and $k$ are best possible: the paper's own constructions satisfy the spectral condition while containing only $\Theta(m^{\frac{s+t-1}{2}})$ or $\Theta(m^k)$ copies, respectively.
  • Theorem 1.6 resolves the order-of-magnitude part of Problem 1.4 for odd cycles; only the sharp asymptotic constant remains open.
  • The case $s=2$, which would cover book graphs, is outside the scope of Theorem 1.5 and is not settled by this paper.

Reading between the lines

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

  • The same $\varepsilon$-core reduction should transfer to any almost-bipartite graph whose edge-spectral extremal construction is a split graph (for instance fan, friendship, or theta graphs), since the proof itself only uses near-bipartiteness plus counting copies through common neighborhoods.
  • The sharp constants left open by the two theorems are likely attained by the split constructions themselves, which would make the constant equal to the number of copies inside $S_{s-1,m}$ (or $H_m$) rather than a value coming from an averaging argument.
  • Because the proof quotes a stability lemma from the authors' earlier work rather than proving it, the robustness of Theorems 1.5 and 1.6 is only as strong as that lemma; a reader wanting full self-containment would need to insert its proof.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 5 minor

Summary. The paper studies edge-spectral supersaturation for two families of 3-chromatic color-critical graphs: the graphs K_{s,t}^+ (complete bipartite K_{s,t} with one additional edge in the part of size s) and odd cycles C_{2k+1}. The main results, Theorem 1.5 and Theorem 1.6, assert that for a large m-edge graph G, the spectral condition rho(G) > g_{s-1}(m) forces Omega(m^{(s+t-1)/2}) copies of K_{s,t}^+, and rho(G) > g_k(m) forces Omega(m^k) copies of C_{2k+1}, with both bounds tight up to constant factors. The proof proceeds by extracting an epsilon-core H from a hypothetical counterexample, applying a stability result to show H is close to a complete bipartite graph, and then counting copies of the forbidden graph through a sequence of structural lemmas. The tightness constructions in Section 3 and Section 6 use split graphs and regular high-girth graphs.

Significance. If the results are correct, they provide the first edge-spectral supersaturation statements in the tripartite, split-threshold regime, extending the existence theorems of Li-Liu-Zhang to optimal polynomial counting bounds and partially resolving Problem 1.4. The paper contains explicit thresholds, matching constructions, and a coherent core-decomposition argument. The main caveat is that the two most powerful tools, Lemmas 2.1 and 2.2, are imported without proof from the authors' companion preprint, so the manuscript is not self-contained at a load-bearing point. I found no free parameters being fit to the target bounds, and the tightness constructions appear correct. The claimed uniqueness of phi in Section 3 is in fact true, although it deserves a proof sketch.

major comments (2)
  1. [§2, Lemma 2.2 (used in §4 after (20))] Lemma 2.2 is the unique source of the near-bipartite structure in the proof of Theorem 1.5. It is applied to the epsilon0-core H to produce the partition (U1,U2) with d(H,K_{U1,U2}) <= epsilon h, and every subsequent step - Lemmas 4.5 through 4.12, the construction of H* in Case 1, and the deletion of internal edges in Case 2 - depends on that partition. The lemma is stated as a black box from the authors' own preprint [4] and is not proved in this manuscript. If Lemma 2.2 has unstated hypotheses that fail for K_{s,t}^+ with t+1=s, the central reduction fails. I request that the proof of Lemma 2.2 be reproduced in the paper or in an appendix, or that a published version with a complete proof be cited, with the hypotheses explicitly checked for all parameter ranges in Theorem 1.5.
  2. [§2, Lemma 2.1 (used in Lemmas 4.1 and 4.2)] Lemma 2.1 is also imported from the companion preprint [4] without proof. It is used in Lemma 4.1 to rule out the possibility that too many edges are removed during the epsilon-core iteration, and in Lemma 4.2 to obtain the upper bound rho(H) < sqrt((1+2epsilon)h). These steps are necessary for the core construction and for the subsequent counting argument. The dependency on an unproved companion-paper result should be resolved in the same way as for Lemma 2.2.
minor comments (5)
  1. [§3, inequality (8)] The uniqueness of phi satisfying (8) is asserted without proof. The assertion is correct: writing phi = 4sn, the intervals (8s^2(2n-1)(n-1), 8s^2 n(2n+1)] partition the positive integers, so exactly one phi exists for every sufficiently large m. A one-sentence justification would remove any doubt.
  2. [§2, Lemma 2.4, equation (4)] The displayed equation appears garbled as 'rho2 =rho 2||z||2 2<=...'. Please correct it to the intended algebraic identity, likely rho^2 = rho z^T A(G[U]) z + z^T B B^T z + (1/2)d, so that the subsequent estimates are readable.
  3. [§1, after Theorem 1.2] The statement that the methodology of [9] 'can be straightforwardly extended' to the case t+1=s is not proved and is not used later. Either provide a proof or explicitly note that the extension is not needed for the arguments in this paper.
  4. [§1.3, discussion of s=2] The phrase 'the case s=2 corresponds to book graphs' is informal; defining the book graph explicitly would help readers who are not specialists in spectral extremal graph theory.
  5. [References] Several key references are arXiv preprints ([4], [7], [8], [9], [10]). If any of these have appeared in refereed journals, the published versions should be cited, especially [4], whose results are load-bearing for the main proof.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the main counting theorems are not assumed as inputs; the cited stability lemmas are general and parameter-free.

full rationale

The proof of Theorem 1.5 proceeds by contradiction: assuming N(K_{s,t}^+,G)=o(m^{(s+t-1)/2}) and ρ(G)>g_{s-1}(m), it extracts an ε0-core H and uses the imported stability result Lemma 2.2 to obtain a near-bipartite partition U1,U2; the rest is a self-contained eigenvector/counting analysis showing such a partition contradicts ρ(H)>g_{s-1}(h). Lemma 2.2 is cited from the authors' own preprint [4], which is a self-citation, but its hypotheses are an upper bound on copies (N(F,G)=o(m^{f/2})) and a spectral-radius lower bound independent of the target lower bound; no fitted parameter is renamed as a prediction and no theorem is defined in terms of its conclusion. The same holds for Lemma 2.1, which is used only to bound ρ(H) above. The tightness constructions are independent, using regular high-girth graphs from Sauer's theorem. Thus the derivation chain does not reduce to its own inputs. The self-citation is a provenance and verification concern, not definitional circularity.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The central claim introduces no free parameters, new constants fitted to data, or invented objects. The split graphs and threshold g_r are prior constructions. The results depend on external theorems cited from [4] and [9].

assumptions (4)
  • domain assumption Li-Liu-Zhang edge-spectral Turan theorem for K_{s,t}^+-free graphs, including the stated extension to t+1=s.
    Used in Section 1.1 to identify g_{s-1}(m) as the analytic threshold and rho(S_{s-1,m}) as its approximate extremal value; the extension is asserted without proof.
  • domain assumption Fang-Lin-Zhai spectral supersaturation lemma (Lemma 2.1) and edge-spectral supersaturation-stability lemma (Lemma 2.2).
    Imported from the same authors' prior preprint [4]; Lemma 2.2 provides the near-bipartite structure that the contradiction proof starts from.
  • standard math Sauer's theorem on the existence of g-regular graphs with prescribed girth.
    Used in Section 3 to build the 4s-regular C4-free graph H* for the sharpness construction.
  • standard math Perron-Frobenius theorem for nonnegative matrices.
    Provides the nonnegative eigenvector x used throughout Section 4; standard in spectral graph theory.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Edge-spectral supersaturation for tripartite color-critical graphs." pith.science (2026). https://pith.science/paper/V52JACE5

@misc{pith2026260804485,
  author       = {Pith},
  title        = {Pith review of: Edge-spectral supersaturation for tripartite color-critical graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V52JACE5}},
  note         = {Machine review of arXiv:2608.04485}
}
abstract

We study edge-spectral supersaturation for two families of color-critical graphs with chromatic number three. For an integer $r\geq 1$, we define the spectral threshold \[ g_r(m):=\frac{r-1+\sqrt{4m-r^2+1}}{2}, \] which is the tight upper bound on the spectral radius of graphs avoiding $K_{s,t}^+$ (when $t+1\geq s\geq 3$) and $C_{2k+1}$ (when $r=k$), realized by split-graph constructions. First, let $t+1 \geq s\geq 3$ be fixed integers, and let $K_{s,t}^{+}$ be obtained by adding an edge to the part of size $s$ in $K_{s,t}$. We prove that every sufficiently large $m$-edge graph $G$ with $\rho(G)>g_{s-1}(m)$ contains $\Omega(m^{(s+t-1)/2})$ copies of $K_{s,t}^{+}$. Second, for any fixed $k\geq 2$, the condition $\rho(G)>g_k(m)$ forces $N(C_{2k+1},G)=\Omega(m^k).$ We also construct graphs showing that both lower bounds are tight up to constant factors. These results establish that exceeding the tight spectral Tur\'{a}n threshold $g_r(m)$ forces not just a single copy, but the optimal polynomial number of copies of these color-critical graphs. Thus, crossing the relevant split-graph spectral threshold forces the optimal polynomial order of copies, extending edge-spectral existence theorems to supersaturation results in the delicate three-chromatic regime.

Review history (3 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 18 canonical work pages

  1. [4]

    L. Fang, H. Lin, M. Zhai, Counting color-critical subgraphs under Nikiforov’s condition, arXiv:2603.14964

    arXiv

  2. [9]

    Y. Li, H. Liu, S. Zhang, Edge-spectral Tur´ an theorems for color-critical graphs with appli- cations, arXiv:2511.15431v2

    arXiv

  3. [1]

    Bollob´ as, V

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

    work page 2007

  4. [2]

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

    arXiv

  5. [3]

    L. Fang, H. Lin, M. Zhai, Stable structure and extremal eigenvalues of degenerate Tur´ an problems,Discrete Math.349(2026), no. 11, Paper No. 115299, 17 pp

    work page 2026

  6. [5]

    S. Li, S. Zhao, L. Zou, Spectral extrema of graphs with fixed size: forbidden a fan graph, a friendship graph, or a theta graph,J. Graph Theory110(2025), no. 4, 483–495

    work page 2025

  7. [6]

    X. Li, M. Zhai, J. Shu, A Brualdi-Hoffman-Tur´ an problem on cycles,European J. Combin. 120(2024), Paper No. 103966, 13 pp

    work page 2024

  8. [7]

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

    arXiv

Show all 26 references
  1. [8]

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

    2026

  2. [10]

    Y. Li, W. Lin, H. Liu, S. Zhang, Spectral Sidorenko inequalities and edge-spectral super- saturation, arXiv:2605.26614v2

    arXiv

  3. [11]

    C. Liu, J. Li, S. Li, Y. Yu, A Brualdi-Hoffman-Tur´ an problem on theta graph,Adv. in Appl. Math.173(2026), part B, Paper No. 103000, 40 pp

    2026

  4. [12]

    Lov´ asz, M

    L. Lov´ asz, M. Simonovits, On the number of complete subgraphs of a graph II,Studies in pure mathematics,Birkh¨ auser, Basel, 1983, pp. 459–495

    1983

  5. [13]

    J. Ma, L. Yuan, Supersaturation beyond color-critical graphs,Combinatorica45(2025), no. 2, Paper No. 18, 40 pp

    2025

  6. [14]

    Mubayi, Counting substructures I: Color critical graphs,Adv

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

    2010

  7. [15]

    Nikiforov, The number of cliques in graphs of given order and size,Trans

    V. Nikiforov, The number of cliques in graphs of given order and size,Trans. Amer. Math. Soc.363(2011), no. 3, 1599–1618

    2011

  8. [16]

    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), no. 2, 179–189

    2002

  9. [17]

    Nikiforov, Walks and the spectral radius of graphs,Linear Algebra Appl.418(2006), no

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

    2006

  10. [18]

    Nikiforov, More spectral bounds on the clique and independence numbers,J

    V. Nikiforov, More spectral bounds on the clique and independence numbers,J. Combin. Theory Ser. B99(2009), no. 6, 819–826

    2009

  11. [19]

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

    2023

  12. [20]

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

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

    1970

  13. [21]

    Pikhurko, Z

    O. Pikhurko, Z. Yilma, Supersaturation problem for color-critical graphs,J. Combin. The- ory Ser. B123(2017) 148–185

    2017

  14. [22]

    Sauer, On the existence of regularn-graphs with given girth,J

    N. Sauer, On the existence of regularn-graphs with given girth,J. Combin. Theory9(1970) 144–147

    1970

  15. [23]

    Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc

    M. Simonovits, A method for solving extremal problems in graph theory, stability problems, Theory of Graphs (Proc. Colloq., Tihany, 1966),Academic Press, New York, 1968, pp. 279– 319

    1966

  16. [24]

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

    2021

  17. [25]

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

    2026

  18. [26]

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

    arXiv

Pith tools

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