REVIEW 3 major objections 6 minor 1 cited by
Spectral extremal problems for degenerate graphs
T0 review · 3 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Spectral extremal graphs for degenerate families are edge-extremal
desk verdict Novel covering framework and attractive applications, but a false density inference in Lemma 3.13 leaves Theorems 1.2 and 1.3 unproven. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the auxiliary family H(F), built from vertex covers: H(F) = K_{β′(F)} if β′(F) = β(F), and otherwise H(F) = M(F), the family of induced subgraphs on covers of size < β′(F). The engine is a spectral stability theorem (Theorem 3.3): if λ(G) is close to λ(K_{β′(F)−1,n+1−β′(F)}), then G contains a large complete bipartite graph K_{β′(F)−1,t} with t > (1 − 2β′(F)$ε^{{1/10}}$)n, and the Perron vector is concentrated, with entries at least 1 − $ε^{{1/10}}$ on the small side and at most $ε^{{1/8}}$ elsewhere. This concentration makes edge-switchings that replace parts of G by the extremal skeleton strictly increase the spectral radius if G deviates, forcing the spectral extremal graph into G(F). A second structural lemma (Lemma 3.13) shows that ex_H(n, F) = e(H) + rn + O(1) for r ∈ {0, 1/2, 2/3}, which is used to pin down the possible forms of the complement part.
What would settle it
Construct a finite degenerate family F with β′(F) ≥ 2 and ex(n,F) = O(n) satisfying ex_H(n,F) < e(H) + ⌊(n+1−β′)/2⌋, but for which some n-vertex F-free graph has spectral radius larger than every graph in G(F) while not containing H = K_{β′−1,n+1−β′} as a subgraph; Theorem 3.3 predicts that for large n such a graph cannot exist.
Extended reading notes
Core claim
The central assertion is Theorem 1.1. Let F be a finite degenerate family with β′(F) ≥ 2 and ex(n, F) = O(n), and set H = K_{β′(F)−1,n+1−β′(F)}. If ex_H(n, F) < e(H) + ⌊(n+1−β′(F))/2⌋, then for sufficiently large n every graph in Exsp(n, F) lies in G(F) = {Ex_H(n, F) : H ∈ G0(F)}, where G0(F) = {T ∨ I_{n+1−β′(F)} : T ∈ Ex(β′(F)−1, H(F))}. In words, after fixing the β′(F)−1 'small side' to be an extremal graph for the auxiliary family H(F), the spectral extremal graph is exactly an edge-extremal extension of this skeleton. The paper also proves Theorem 1.3, showing Exsp(n, F) ⊆ G(F) ⊆ Ex(n, F) when certain sparse extensions are already edge-extremal, and Theorem 1.4, giving the explicit classification for forbidden long cycles plus a graph.
Load-bearing premise
The proof collapses if the forbidden family's Turán number is not linear: the Perron-vector concentration bound |L_η| ≤ D(η, ε)√n, and with it the identification of the β′(F)−1 vertex core and its huge common neighborhood, depends on ex(n,F) = O(n).
Editorial extensions
If this is right
- For any finite degenerate family satisfying the hypotheses of Theorem 1.1, the spectral extremal problem reduces to the ordinary edge-extremal problem on a fixed skeleton; in particular Exsp(n, F) ⊆ G(F) for all large n.
- The matching-plus-arbitrary-graph family F = {M_{s+1}, F} has spectral extremal graphs inside Ex(n, F) when β′(F) = s+1, and inside G(F) otherwise (Theorem 2.3), recovering Exsp(n, {M_{s+1}, K_{r+1}}) = G(n, r, s).
- For F = {C_{≥k}, F} with β′(F) = ⌊(k+1)/2⌋, the spectrum-maximizing graphs are exactly the joins T ∨ I_{n−⌊(k−1)/2⌋} (k odd), or T ∨ I_{n−k/2+1} or T ∨ (K2 ∪ I_{n−k/2−1}) (k even), where T ranges over the appropriate Ex(·, H(F)) family.
- When the sparse extensions T ∨ eH are themselves edge-extremal, with e(eH) ≤ rn + O(1) and r < 3/4, every spectral extremal graph is an ordinary extremal graph: Exsp(n, F) ⊆ G(F) ⊆ Ex(n, F).
- Several previously known spectral theorems, for forbidden matchings plus cliques, linear forests, long cycles, and the spectral Erdős–Sós statement, follow as corollaries.
Reading between the lines
- The form of Theorem 1.1 suggests a broader conservation law: whenever a degenerate family has a linear Turán number, the spectral radius maximizer may be determined by edge counts alone on the small core plus sparsity of the complement; this may hold for weak finite degenerate families even without full finiteness, since the stability theorem is stated in that weaker setting.
- The dichotomy in Lemma 3.13, where the surplus r can only be 0, 1/2, or 2/3 according to whether the complement part has O(1) edges, a near-perfect matching, or many P3-components, indicates a general classification of extremal complements by component type; one could test whether every family satisfying the sparse-extension hypothesis falls into one of these three regimes.
- A direct testable extension is to replace the spectral radius by other eigenvalue functionals, such as the signless Laplacian spectral radius, and check whether the same small-core characterization holds under identical hypotheses.
- The stability theorem's dependence on the size l = |F0| of the bipartite witness suggests that the threshold for 'sufficiently large n' grows with l; quantifying this dependence could yield effective bounds instead of purely asymptotic statements.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper develops a spectral stability theorem (Theorem 3.3) for weakly finite degenerate graph families with linear Turán number, using Perron-vector concentration estimates. It then derives three general characterizations of spectral extremal graphs for finite degenerate families (Theorems 1.1–1.3) and one result for infinite families of the form {C≥k,F} (Theorem 1.4), together with a set of applications recovering or extending known results of Wang–Hou–Ma, Zhai–Yuan, Wang–Feng–Lu, and others. The main structural conclusion is that, under the stated hypotheses, every spectral extremal graph has the form T ∨ Q where T is an extremal graph for the auxiliary family H(F) on β′(F)−1 vertices and Q lies in a corresponding Turán-type extremal class.
Significance. If the main theorems are correct, the paper provides a broad framework for spectral extremal problems of degenerate families, reducing the problem to a finite Turán-type question on a small vertex set. The Perron-vector stability argument is a substantial technical contribution, and the explicit recovery of several published results is valuable. The paper is not machine-checked, but the epsilon-delta structure of Theorem 3.3 is coherent. However, the proof of Lemma 3.13, which is load-bearing for Theorems 1.2 and 1.3, contains a genuine logical gap, and the derivation of Theorem 2.7 applies a finite-family result to an infinite family without justification. These issues do not necessarily invalidate the paper's program, but they require a substantive repair before the intermediate-density claims can be accepted.
major comments (3)
- [Section 3, Lemma 3.13] The proof of Lemma 3.13 contains an invalid density inference. The text states: 'If |B′′| ≥ 4, then e(B′′) ≥ |B′′|−1 ≥ 3/4 |B′′|, which implies that the number of components of order at least 4 is O(1).' This implication is false: a linear number of 4-vertex components, for example n/2 vertices split into n/8 disjoint P4 components with the remaining n/2 vertices isolated, has ω(1) components of order 4 and excess 3n/8, which is compatible with ex_H(n,F) ≤ e(H)+rn+O(1) for any r ≥ 3/8 and in particular for r < 3/4. Consequently the definition of p and the conclusion r ∈ {0,1/2,2/3} are not established by the given argument. The same unproven structural claim is reused in Lemma 3.14, whose first sentence asserts that components of Q have size O(1). Since Lemma 3.13 is invoked directly in the proofs of Theorems 1.2 and 1.3 (Sections 4.2 and 4.3) and indirectly in Theorems 2.2 and 2.3, the intermediate-density spectral classification currently rests on an unsupported dichotomy. The authors need either to provide a correct argument ruling out components of order at least 4 via F-freeness and extremality, or to revise the claimed classification.
- [Section 2, Theorem 2.7] The proof of Theorem 2.7 applies Corollary 2.6 to the family F consisting of all finite graphs that contain all trees on 2t+2 vertices. Corollary 2.6, however, is stated for a finite degenerate family J, and its proof relies on Theorem 1.1, which assumes F is finite. The finiteness of the forbidden family is used in essential places, notably in Theorem 3.3 to fix a bounded bipartite graph F0 and in Lemma 3.12 for the replacement argument. No extension to infinite families of this kind is proved in the paper. Therefore the claimed derivation of the Wang–Feng–Lu spectral Erdős–Sós-type theorem is not justified as written, even though the theorem itself may be true and known.
- [Section 3, Lemma 3.13] A further issue in the same lemma is the argument used to limit isolated vertices in the p=2 case. The sentence '(F1 \ e1) ∪ e2 is a copy of F1 in G' is only meaningful if the edge e2 can be embedded in place of e1 while preserving the rest of the copy. The proof should spell out that, because all vertices of B are joined to every vertex of A, an edge e2 can be chosen with endpoints outside the copy and with the same adjacencies to A as the endpoints of e1. As written, the replacement step is too terse and, taken literally, is not valid for an arbitrary finite graph F1.
minor comments (6)
- [Section 1.1] There is a typo: 'A matching of size of size s + 1' repeats 'of size'.
- [Section 3, Lemma 3.5] In equations (1) and (2) the two sums over L^η_1(u) appear with identical notation, although one of them should presumably involve the complement L^η_1(u). Please correct the typesetting and clarify the two different index sets.
- [Section 3, Lemma 3.7] The pigeonhole step bounding |S| is compressed: the inequality |S|/binom(|L1(u)∪L2(u)|, β′−1) > sqrt(n)/binom(|L|, β′−1) > l needs a short justification using |L| ≤ m(ε) and the fact that binom(|L|, β′−1) is polynomial in n. Please spell out the constants.
- [Section 2, Theorem 2.7] The symbol F is used both for the family of all graphs containing all trees of order 2t+2 and for the arbitrary graph in the theorem statement. Please disambiguate the notation.
- [References] Reference [6] and reference [9] are the same paper (Cioabă, Desai, and Tait, 'A spectral Erdős–Sós theorem'), and references [26] and [29] are the same Nikiforov paper. Please remove the duplicates.
- [Throughout] The phrases 'the number of components ... is infinite' in Lemma 3.13 should be quantified as 'unbounded as n grows' to make the asymptotic reasoning precise.
Circularity Check
No significant circularity: the main theorems are derived from a self-contained spectral stability theorem, and cited prior work is used as external input or background, not to define the conclusions.
full rationale
The paper's central derivation chain is self-contained. The stability result (Theorem 3.3) is proved directly through the Perron-vector lemmas in Section 3, using only the linearity assumption ex(n,F) = O(n) as an input hypothesis; it does not assume the spectral extremal classification it later produces. Theorems 1.1-1.4 then deduce the structure of Exsp(n,F) from this stability theorem plus extremal-edge counting arguments, and the target graph families G0(F), G(F) are definitions, not fitted or renamed conclusions. No parameter is fitted to a subset of data and then called a prediction, and no uniqueness theorem from the authors' own prior work is invoked to force the choice of extremal skeleton. The citations to prior work, including Byrne-Desai-Tait [3], Alon-Frankl [1], Cioaba-Desai-Tait [9], and others, serve as external results for applications, corollaries, or background, and are not load-bearing in a way that reduces the main claim to those citations. The flagged concern about Lemma 3.13's density inference ('If |B''| >= 4, then e(B'') >= |B''|-1 >= 3/4 |B''|, which implies that the number of components of order at least 4 is O(1)') is a potential correctness gap in an auxiliary structural argument, not a circularity: even if the inference fails, the theorem would be unproven rather than true-by-definition. Accordingly, the circularity score is 0.
Assumptions & free parameters
assumptions (9)
- standard math Perron-Frobenius theorem: a nonnegative irreducible matrix has a positive eigenvector for its spectral radius.
- standard math Wu-Xiao-Hong spectral switching lemma (Lemma 3.1): moving edges to higher-eigenvector vertices increases spectral radius.
- standard math Chvátal-Hanson bound: e(G) ≤ ν(G)(Δ(G)+1) for any graph.
- standard math Erdős-Gallai theorem: ex(n,C≥k) ≤ (k-1)(n-1)/2.
- standard math Cayley formula: number of labeled trees on s vertices is s^{s-2}.
- standard math Cioabă-Desai-Tait bound: ex_{K_{t,n-t}}(n,T) ≤ e(K_{t,n-t}) + binom(t,2) for any tree T of order t.
- standard math Alon-Frankl theorem: Ex(n,{M_{s+1},K_{r+1}}) = G(n,r,s) for large n.
- standard math Zhu-Chen theorem: Ex(n,{M_{s+1},F}) = {T ∨ I_{n-s} | T ∈ Ex(s,H(F))} when β'(F)=s+1.
- standard math Dou-Ning-Peng theorem: Turán number of {C≥k,K_{r+1}}.
Cite this review
Pith. "Pith review of Spectral extremal problems for degenerate graphs." pith.science (2026). https://pith.science/paper/NVELVHEK
@misc{pith2026250712014,
author = {Pith},
title = {Pith review of: Spectral extremal problems for degenerate graphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/NVELVHEK}},
note = {Machine review of arXiv:2507.12014}
}
abstract
A family of graphs is called degenerate if it contains at least one bipartite graph. In this paper, we investigate the spectral extremal problems for a degenerate family of graphs $\mathcal{F}$. By employing covering and independent covering of graphs, we establish a spectral stability result for $\mathcal{F}$. Using this stability result, we prove two general theorems that characterize spectral extremal graphs for a broad class of graph families $\mathcal{F}$ and imply several new and known results. Meanwhile, we establish the correlation between extremal graphs and spectral extremal graphs for $\mathcal{F}$.
Forward citations
Cited by 1 Pith paper
-
Tensor Spectral Stability for Uniform Hypergraphs with Bounded Matching Number
Near-maximal tensor spectral radius forces a k-graph with matching number ≤β to be structurally close to S_{n,k,β} for large n.
Reference graph
Works this paper leans on
-
[1]
N. Alon, P. Frankl, Tur ´an graphs with bounded matching number, J. Comb. Theory, Ser. B 165 (2024) 223-229
work page 2024
-
[2]
J. Byrne, A sharp spectral extremal result for general non-bipartite graphs, arXiv preprint arXiv: 2411.18637, (2024)
-
[3]
J. Byrne, D.N. Desai, M. Tait, A general theorem in spectral extremal graph theory, arXiv preprint arXiv: 2401.07266, (2024)
arXiv 2024
-
[4]
M. Chen, A. Liu, X. Zhang, Spectral Extremal Results with Forbidding Linear Forests, Graphs and Comb. 35 (2019) 335-351
work page 2019
-
[5]
M. Chen, A. Liu, X. Zhang, On the spectral radius of graphs without a star forest, Discrete Math. 344(4) (2021) 112269
work page 2021
-
[7]
P ´eter Csikv´ari, Applications of the Kelmans transformation: extremality of the threshold graphs, Electron. J. Comb. 18 (2011) #P182. 23
work page 2011
-
[8]
S. Cioab ˘a, D.N. Desai, M. Tait, The spectral radius of graphs with no odd wheels, Eur. J. Comb. 99 (2022) 103420
work page 2022
-
[9]
S. Cioab ˘a, D.N. Desai, M. Tait, A spectral Erd˝os-S´os theorem, SIAM J. Discrete Math. 37(3) (2023) 2228- 2239
work page 2023
Show all 39 references
-
[10]
Cioab ˘a, D.N
S. Cioab ˘a, D.N. Desai, M. Tait, The spectral even cycle problem, Comb. Theory 4(1) (2024) 10
2024
-
[11]
Chv´atal, D
V . Chv´atal, D. Hanson, Degrees and matchings, J. Comb. Theory, Ser. B 20 (1976) 128-138
1976
-
[12]
C. Dou, F. Hu, X. Peng, Tur ´an numbers of cycles plus a general graph, arXiv preprint arXiv:2411.17322, (2024)
2024 arXiv
-
[13]
C. Dou, B. Ning, X. Peng, The number of edges in graphs with bounded clique number and circumference, arXiv preprint arXiv:2410.06449, (2024)
2024 arXiv
-
[14]
Erd ˝os, T
P. Erd ˝os, T. Gallai, On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hung. 10 (1959) 337- 356
1959
-
[15]
Erd ˝os, M
P. Erd ˝os, M. Simonovits, A limit theorem in graph theory, Studia Sci. Math. Hungar. 1 (1966) 51-57
1966
-
[16]
F ¨uredi, M
Z. F ¨uredi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, Erd ˝os centennial, 169-264, Bolyai Soc. Math. Stud., 25, J´anos Bolyai Math. Soc., Budapest, 2013
2013
-
[17]
L. Fang, M. Tait, M. Zhai, Decomposition family and spectral extremal problems on non-bipartite graphs, Discrete Math. 348 (2025) 114527
2025
-
[18]
L. Fang, H. Lin, J. Shu, Z. Zhang, Spectral extremal results on trees, Electron. J. Comb. 31(2) (2024), #P2.34
2024
-
[19]
X. Fang, X. Zhu, Y . Chen, Generalized Tur ´an problem for a path and a clique, Eur. J. Comb. 127 (2025) 104137
2025
-
[20]
L. Feng, G. Yu, and X. Zhang, Spectral radius of graphs with given matching number, Linear Algebra Appl. 422(1) (2007) 133-138
2007
-
[21]
Gao and X
J. Gao and X. Hou, The spectral radius of graphs without long cycles, Linear Algebra Appl. 566 (2019) 17-33
2019
-
[22]
Gerbner, On Tur ´an problems with bounded matching number, J
D. Gerbner, On Tur ´an problems with bounded matching number, J. Graph Theory 106 (2024) 23-29
2024
-
[23]
Jiang, Y
S. Jiang, Y . Zhai, X. Yuan, Some stability results for spectral extremal problems of graphs with bounded matching number, Linear Algebra Appl. 708 (2025) 513-524
2025
-
[24]
Katona, C
G. Katona, C. Xiao, Extremal graphs without long paths and large cliques, Eur. J. Comb. 119 (2024) 103807
2024
-
[25]
Y . Liu, L. Kang, Extremal graphs without long paths and a given graph, Discrete Math. 347 (2024) 113988
2024
-
[26]
Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl
V . Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432(9) (2010) 2243-2256
2010
-
[27]
Nikiforov, Merging theA- and Q-spectral theories, Appl
V . Nikiforov, Merging theA- and Q-spectral theories, Appl. Anal. Discrete Math. 11(1) (2017) 81-107. 24
2017
-
[28]
Nikiforov, Some new results in extremal graph theory
V . Nikiforov, Some new results in extremal graph theory. Surveys in combinatorics 2011, 141-181, London Math. Soc. Lecture Note Ser., 392, Cambridge Univ. Press, Cambridge, 2011
2011
-
[29]
Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl
V . Nikiforov, The spectral radius of graphs without paths and cycles of specified length, Linear Algebra Appl. 432 (2010) 2243-2256
2010
-
[30]
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, pp. 279-319
1966
-
[31]
T. Wang, L. Feng, L. Lu, Spectral extremal problems for graphs with bounded clique number, Linear Algebra Appl. 710 (2025) 273-295
2025
-
[32]
H. Wang, X. Hou, Y . Ma, Spectral extrema of graphs with bounded clique number and matching number, Linear Algebra Appl. 669 (2023) 125-135
2023
-
[33]
J. Wang, L. Kang, Y . Xue, On a conjecture of spectral extremal problems, J. Comb. Theory, Ser. B 159 (2023) 20-41
2023
-
[34]
B. Wu, E. Xiao, Y . Hong, The spectral radius of trees on k pendant vertices, Linear Algebra Appl. 395 (2005) 343-349
2005
-
[35]
Y . Xue, L. Kang, On generalized Tur ´an problems with bounded matching number, arXiv preprint arXiv:2410.12338, (2024)
2024 arXiv
-
[36]
L. Yuan, X. Zhang, Tur ´an numbers for disjoint paths, J. Graph Theory 98 (2021) 499-524
2021
-
[37]
X. Zhu, Y . Chen, Extremal problems for a matching and any other graph, J. Graph Theory 109 (2025) 19-24
2025
-
[38]
X. Zhao, M. Lu, Generalized Tur ´an problems for a matching and long cycles, arXiv preprint arXiv:2412.18853, (2024)
2024 arXiv
-
[39]
Y . Zhai, X. Yuan, Spectral extrema of{Kk+1, Ls}-free graphs, Linear Algebra Appl. 682 (2024) 309-322
2024
-
[40]
Y . Zhai, X. Yuan, L. You, Spectral extrema of graphs: Forbidden star-path forests, Discrete Math. 348 (2025) 114351. 25
2025
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.