pith. sign in

arxiv: 2607.01073 · v1 · pith:X3G7AWNBnew · submitted 2026-07-01 · 🧮 math.CO

An edge-spectral supersaturation of Mubayi's theorem for color-critical graphs

Hongzhang Chen , Yongtao Li This is my paper

Pith reviewed 2026-07-02 10:13 UTC · model grok-4.3

classification 🧮 math.CO
keywords supersaturationspectral radiuscolor-critical graphsMubayi's theoremextremal graph theoryadjacency spectral radiusforbidden subgraphsTurán graphs
0
0 comments X

The pith

For color-critical F with χ(F)≥4, spectral surplus q forces (B_F-o(1)) q m^{(f-2)/2} copies of F with sharp constant B_F.

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

The paper proves that when an m-edge graph exceeds the known spectral extremal threshold 2(1-1/r)m by a small surplus q (at most order sqrt(m)), it must contain at least roughly B_F q m to the power (f-2)/2 copies of any color-critical forbidden subgraph F. This matters to a sympathetic reader because it turns a tiny spectral excess into a guaranteed linear number of copies, with an explicit best-possible prefactor B_F = α_F/4 times (2r/(r-1)) to the f/2. The result supplies the edge-spectral version of Mubayi's supersaturation theorem and solves the Fang-Lin-Zhai conjecture in stronger form. It applies uniformly to all color-critical F with chromatic number r+1 at least 4.

Core claim

For every color-critical graph F with χ(F)=r+1≥4, there exists δ_F>0 such that if m is sufficiently large, 0<q≤δ_F√m, and G is an m-edge graph with λ²(G)≥2(1−1/r)m+q, then N_F(G)≥(B_F−o(1)) q m^{(f−2)/2}, where B_F:=α_F/4 (2r/(r−1))^{f/2}, and the constant B_F is best possible. This converts the spectral surplus q into a linear number of copies with a sharp constant, and it solves the conjecture of Fang, Lin and Zhai in a stronger form.

What carries the argument

The spectral surplus q = λ²(G) − 2(1−1/r)m, which is converted by the counting argument into a linear lower bound on N_F(G) with prefactor B_F.

If this is right

  • Mubayi's theorem extends to the spectral-radius setting with the identical sharp constant B_F.
  • The Fang-Lin-Zhai conjecture is settled in stronger form: the number of copies grows linearly with the surplus q rather than only polynomially.
  • For q in the allowed range the o(1) term vanishes, yielding an asymptotic lower bound linear in q.
  • The extremal examples achieving the constant B_F in the limit are suitable perturbations of the balanced complete r-partite Turán graphs.

Where Pith is reading between the lines

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

  • The linear dependence on q may allow similar supersaturation statements for other spectral or matrix-norm extremal problems that admit stability.
  • For concrete small F such as K_4 one could run numerical checks on random or perturbed graphs with a few hundred edges to test whether the predicted constant B_F appears.
  • The result suggests the copy count N_F(G) behaves continuously with respect to the spectral surplus near the threshold, which could be used to study the width of the supersaturation window.

Load-bearing premise

The restriction that q is at most δ_F times sqrt(m) for some positive δ_F depending only on F, which is required to make the error term o(1) and keep the lower bound linear in q.

What would settle it

An m-edge graph G satisfying λ²(G) = 2(1−1/r)m + q with q ≤ δ_F sqrt(m) but N_F(G) < (B_F/2) q m^{(f−2)/2} for arbitrarily large m would disprove the claim.

Figures

Figures reproduced from arXiv: 2607.01073 by Hongzhang Chen, Yongtao Li.

Figure 1
Figure 1. Figure 1: Proof outline of Theorem 1.4. 8 [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
read the original abstract

We study the supersaturation problem in its edge-spectral form. Let $\lambda(G)$ be the adjacency spectral radius of $G$. Nikiforov proved that every $K_{r+1}$-free graph $G$ with $m$ edges satisfies $\lambda (G)\le \sqrt{(1\!-\!1/r )2m}$. Recently, Li, Liu and Zhang proved the same bound for every $F$-free graph $G$, where $F$ is any color-critical graph with $\chi(F)=r+1\ge4$, with equality only for regular complete $r$-partite graphs. It is then natural to ask how many copies of $F$ are forced once $\lambda (G)$ exceeds this threshold. Fang, Lin and Zhai answered this at the threshold itself, and conjectured that for any fixed $C>0$, the condition $\lambda (G)\ge \sqrt{(1\!-\!{1}/{r})2m} +C$ forces $\Omega\!\left(m^{(f-1)/2}\right)$ copies. In this paper, we answer this question with the best possible constant, proving that for every color-critical graph $F$ with $\chi(F)=r+1\ge4$, there exists $\delta_F>0$ such that if $m$ is sufficiently large, $0<q\le\delta_F\sqrt m$, and $G$ is an $m$-edge graph with $\lambda^2(G)\ge 2\left(1-\tfrac1r\right)m+q$, then \[ N_F(G)\ge\bigl(B_F-o(1)\bigr)\,q\, m^{{(f-2)}/{2}}, \quad \text{where}~~ B_F:=\tfrac{\alpha_F}{4} (\tfrac{2r}{r-1} )^{{f}/{2}}, \] and the constant $B_F$ is best possible. Our result can be viewed as an edge-spectral counterpart of Mubayi's theorem, since it converts the spectral surplus $q$ into a linear number of copies with a sharp constant, and it solves the conjecture of Fang, Lin and Zhai in a stronger form.

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 / 2 minor

Summary. The manuscript proves an edge-spectral supersaturation result for color-critical graphs F with χ(F)=r+1≥4. For an m-edge graph G satisfying λ²(G)≥2(1−1/r)m + q with 0<q≤δ_F √m (m large), it establishes N_F(G)≥(B_F−o(1)) q m^{(f−2)/2} where B_F=α_F/4 (2r/(r−1))^{f/2} is best possible. This is framed as an edge-spectral analogue of Mubayi's theorem that strengthens the conjecture of Fang, Lin and Zhai.

Significance. If correct, the result supplies a sharp explicit constant for spectral supersaturation, directly converting a small spectral surplus q into a linear number of F-copies with the optimal prefactor B_F. The restriction to the regime q=O(√m) together with the best-possible constant constitute a precise quantitative advance over threshold-only results.

major comments (1)
  1. [Abstract (main theorem)] Abstract (main theorem statement): the linear lower bound with o(1) term is load-bearing on the hypothesis 0<q≤δ_F √m; the manuscript must verify that the stability or perturbation argument controlling the excess edges produces an error o(q) precisely when the surplus remains below the natural √m scale of the Turán graph, as larger q may allow higher-order global contributions to dominate the counting.
minor comments (2)
  1. [Abstract] The symbols f (order of F) and α_F are used without explicit definition in the abstract; they should be introduced at first appearance in the introduction or theorem statement.
  2. [Introduction] Notation for λ(G) (adjacency spectral radius) and N_F(G) (number of copies) is standard but should be recalled once in the introduction for self-contained reading.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading, the positive assessment, and the recommendation for minor revision. The single major comment is addressed below; we agree that an explicit verification of the error control is helpful and will incorporate a clarifying remark.

read point-by-point responses

  1. Referee: [Abstract (main theorem)] Abstract (main theorem statement): the linear lower bound with o(1) term is load-bearing on the hypothesis 0<q≤δ_F √m; the manuscript must verify that the stability or perturbation argument controlling the excess edges produces an error o(q) precisely when the surplus remains below the natural √m scale of the Turán graph, as larger q may allow higher-order global contributions to dominate the counting.

    Authors: We thank the referee for this observation. The restriction q ≤ δ_F √m is chosen precisely so that the stability result (Lemma 2.3) yields a graph whose edge excess over the balanced complete r-partite graph is O(q), and the subsequent perturbation analysis in the proof of Theorem 1.1 (equations (3.5)–(3.12)) produces an additive error of o(q) m^{(f−2)/2}. Concretely, the quadratic and higher-order terms arising from the global structure are bounded by O(q²/√m + q^{3/2}), which is o(q) uniformly for q ≤ δ_F √m when δ_F is taken sufficiently small (depending only on F and r). This is why the o(1) term is valid exactly in the stated range; for q ≫ √m the same linear prefactor B_F need not hold. To make the dependence on the √m scale fully explicit we will insert a short explanatory paragraph after the statement of Theorem 1.1. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper states a new supersaturation theorem converting spectral surplus q into N_F(G) ≳ q m^{(f-2)/2} with explicit constant B_F derived from α_F and r. The proof builds on the prior spectral stability result of Li-Liu-Zhang (cited for the base equality case) but the central counting step and the regime q ≤ δ_F √m are presented as technical conditions for the o(1) error, not as a definitional reduction or fitted input renamed as prediction. No self-definitional loop, no ansatz smuggled via citation, and the best-possible claim for B_F rests on separate extremal constructions. The derivation chain therefore contains independent content and does not reduce to its inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on the standard definition of color-critical graphs, the known Nikiforov bound for the spectral radius of K_{r+1}-free graphs, and asymptotic counting arguments typical in extremal graph theory; no new entities or fitted parameters are introduced in the statement.

axioms (2)
  • domain assumption F is color-critical with χ(F)=r+1≥4
    Hypothesis of the main theorem.
  • standard math The Nikiforov bound λ(G)≤√((1-1/r)2m) holds for F-free graphs
    Cited as the threshold being exceeded.

pith-pipeline@v0.9.1-grok · 5952 in / 1454 out tokens · 33786 ms · 2026-07-02T10:13:36.689802+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

48 extracted references · 10 canonical work pages · 2 internal anchors

  1. [1]

    Balogh, F.C

    J. Balogh, F.C. Clemen, On stability of the Erd˝ os–Rademacher problem, Illinois J. Math. 67 (1) (2023) 1–11

    2023

  2. [2]

    Bollob´ as, V

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

    2007

  3. [3]

    Chao, H.-H

    T.-W. Chao, H.-H. H. Yu, When entropy meets Tur´ an: New proofs and hypergraph Tur´ an results, J. Lond. Math. Soc., 113 (3) (2026), Paper No. e70473

    2026

  4. [4]

    H. Chen, Y. Li, Q. Tang, More on Ning–Zhai’s spectral theorem: Triangles and books, (2026), submitted for publication

    2026

  5. [5]

    Cioab˘ a, L

    S. Cioab˘ a, L. Feng, M. Tait, X.-D. Zhang, The maximum spectral radius of graphs without friendship subgraphs, Electron. J. Combin. 27 (4) (2020), #P4.22

    2020

  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) 122–127

    1962

  7. [7]

    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 (1) (1964) 53–56

    1964

  8. [8]

    Erd˝ os, M

    P. Erd˝ os, M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (2) (1983) 181–192

    1983

  9. [9]

    L. Fang, Y. Li, H. Lin, J. Ma, Spectral supersaturation for color-critical graphs, (2025), arXiv:2512.22482. 19

    work page arXiv 2025

  10. [10]

    L. Fang, Y. Li, H. Lin, More on spectral supersaturation for the bowtie, (2026), arXiv:2601.04671

    work page arXiv 2026

  11. [11]

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

    work page arXiv 2026

  12. [12]

    L. Kang, V. Nikiforov, Extremal problems for the p-spectral radius of graphs, Electron. J. Combin. 21 (2014), Paper No. 3.21

    2014

  13. [13]

    M. Kang, T. Makai, O. Pikhurko, Supersaturation problem for the bowtie, European J. Combin. 88 (2020), Paper No. 103107

    2020

  14. [14]

    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 Theory, 110 (4) (2025) 483–495

    2025

  15. [15]

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

    2024

  16. [16]

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

    2025

  17. [17]

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

    2025

  18. [18]

    Y. Li, L. Feng, Y. Peng, A spectral Lov´ asz–Simonovits theorem, (2024), arXiv:2408.01709

    work page arXiv 2024

  19. [19]

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

    2026

  20. [20]

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

    work page arXiv 2025

  21. [21]

    Y. Li, H. Liu, S. Zhang, Edge-spectral Tur´ an theorems for color-critical graphs with applications, (2025), arXiv:2511.15431

    work page arXiv 2025

  22. [22]

    Y. Li, W. Lin, H. Liu, S. Zhang, Spectral Sidorenko inequalities and edge-spectral supersatura- tion, (2026), arXiv:2605.26614

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  23. [23]

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

    2026

  24. [24]

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

    2020

  25. [25]

    X. Liu, D. Mubayi, On a generalized Erd˝ os–Rademacher problem, J. Graph Theory 100 (2022) 101–126

    2022

  26. [26]

    Z. Lou, L. Lu, M. Zhai, A refinement on spectral Mantel’s theorem, European J. Combin., 127 (2025), Paper No. 104142

    2025

  27. [27]

    Lov´ asz, M

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

    1975

  28. [28]

    Lov´ asz, M

    L. Lov´ asz, M. Simonovits, On the number of complete subgraphs of a graph II, in: Studies in Pure Math, Birkh¨ auser (dedicated to P. Tur´ an), 1983, pp. 459–495

    1983

  29. [29]

    Ma, L.-T

    J. Ma, L.-T. Yuan, Supersaturation beyond color-critical graphs, Combinatorica 45 (2) (2025), Paper No. 18

    2025

  30. [30]

    J. Ma, T. Wang, T. Zhu, On clique-to-clique densities, (2026), arXiv:2606.31967

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  31. [31]

    Mubayi, Counting substructures I: Color critical graphs, Adv

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

    2010

  32. [32]

    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

  33. [33]

    Nikiforov, Walks and the spectral radius of graphs, Linear Algebra Appl

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

    2006

  34. [34]

    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. B 99 (6) (2009) 819–826

    2009

  35. [35]

    Nikiforov, Spectral saturation: Inverting the spectral Tur´ an theorem, Electron

    V. Nikiforov, Spectral saturation: Inverting the spectral Tur´ an theorem, Electron. J. Combin., 16 (1) (2009), Paper No. 33

    2009

  36. [36]

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

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

    work page arXiv 2021

  37. [37]

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

    2023

  38. [38]

    B. Ning, M. Zhai, Counting substructures and eigenvalues II: Quadrilaterals, Electron. J. Combin., 32 (4) (2025), Paper No. 4.1

    2025

  39. [39]

    Pikhurko, Z.B

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

    2017

  40. [40]

    Reiher, The clique density theorem, Ann

    C. Reiher, The clique density theorem, Ann. of Math. 184 (3) (2016) 683–707

    2016

  41. [41]

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

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

    1966

  42. [42]

    Tur´ an, On an extremal problem in graph theory, Mat

    P. Tur´ an, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941), pp. 436–452. (in Hungarian)

    1941

  43. [43]

    Wilf, Spectral bounds for the clique and independence numbers of graphs, J

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

    1986

  44. [44]

    Xiao, G.O

    C. Xiao, G.O. Katona, The number of triangles is more when they have no common vertex, Discrete Math. 344 (2021), No. 112330

    2021

  45. [45]

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

    2021

  46. [46]

    M. Zhai, R. Li, Z. Lou, Advances on two spectral conjectures regarding booksize of graphs, (2026), arXiv:2601.10163

    work page arXiv 2026

  47. [47]

    Zheng, Y

    J. Zheng, Y. Li, H. Li, The signless Laplacian spectral Tur´ an problems for color-critical graphs, Linear Algebra Appl. 730 (2026) 546–565

    2026

  48. [48]

    Zheng, Y

    J. Zheng, Y. Li, Y.-Z. Fan, Some Tur´ an-type results for the signless Laplacian spectral radius, European J. Combin. 135 (2026), Paper No. 104373. 21

    2026