{"id":"bef048dc-3148-4904-9f5f-2e3de3368f83","arxiv_id":"2507.12014","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For finite degenerate graph families with linear ex(n,F), the spectral extremal graph is characterized by the independent covering number β'(F) and the induced family H(F).","lead":"This paper determines the spectral-radius-maximizing graphs among large graphs that avoid any graph from a 'degenerate' family (a family containing a bipartite graph), under a linear Turán number condition. The result is a general framework that recovers and extends many existing spectral Turán theorems via a clean covering-number parameter.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 3.13's proof uses a false density inference to restrict components, leaving Theorems 1.2 and 1.3 without a proven structural dichotomy.","rationale":"The paper's central results are the classification theorems in Section 4. The reader's weakest_assumption correctly identifies the linearity hypothesis ex(n,F)=O(n) as an input to the Perron-vector concentration in Theorem 3.3; that is a legitimate concern. However, my reading found a more concrete and more central defect: the proof of Lemma 3.13 makes a quantifier error when it infers from e(B'') ≥ 3/4|B''| that the number of components of order at least 4 is O(1). Unboundedly many bounded-size components can have total size o(n), so the inference fails even under the lemma's own hypotheses. Since Theorem 1.2 and Theorem 1.3 both call Lemma 3.13 to force r to be exactly 1/2 or 2/3, the intermediate regime of the spectral extremal characterization is not rigorously established. I recommend CONDITIONAL rather than REJECT because the final trichotomy may still be true for deeper F-dependent reasons; what is missing is a correct proof of the dichotomy. The proposed computational check would settle whether the lemma itself is false, while the alternative analytic check would indicate whether the proof can be repaired. This does not diminish the paper's substantial contributions: Theorem 1.1 and the applications that rely only on Lemma 3.12 and Lemma 4.1 are not affected by this specific gap, and the paper contains several new and interesting results. The verdict should remain conditional pending a repair of Lemma 3.13 or a demonstration that the missing density argument can be supplied from F-freeness.","tokens_in":26768,"tokens_out":41787,"duration_ms":473749,"concrete_test":"Run an exhaustive search for β'(F)=2, H=K_{1,n-1}: for n up to 14, take F to be each finite degenerate family generated by small bipartite graphs with β'=2 (P4, 2K2, C4, K_{2,3}, P5, and small unions) and compute ex_H(n,F) exactly by brute force. If for any such F the excess ex_H(n,F)−e(H) is not within O(1) of {0,1/2,2/3}n, Lemma 3.13 is false. Separately, attempt to replace the invalid density inference with an F-freeness argument showing that any component of order at least 4 forces, together with the K_{β'−1} side of H, a forbidden subgraph; if no such argument can be given for some admissible F, the proof of the trichotomy remains incomplete.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Lemma 3.13 concludes that under ex_H(n,F) ≤ e(H)+r n+O(1) with r<3/4, the excess over H must be r n+O(1) with r∈{0,1/2,2/3}. The proof's key step reads: '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: infinitely many 4-vertex components can occupy o(n) vertices, e.g., n/2 vertices split into P4 components and n/2 isolated vertices give excess 3/8 n, consistent with any r in [0,3/4) and with infinitely many order-4 components. The subsequent definition of p as the largest order with infinitely many components is therefore unjustified: p could be 4 or larger, and the trichotomy r∈{0,1/2,2/3} does not follow from the stated argument. This is not a cosmetic gap: Lemma 3.13 is used directly in the proofs of Theorems 1.2 and 1.3 (and in Theorem 2.2 and 2.3 via those theorems), so the spectral classification for the intermediate-density regime currently rests on an unproven structural claim. The reader's concern about Theorem 2.7 applying a finite-family corollary to an infinite family is real but is an application-level issue; the Lemma 3.13 gap threatens the core machinery itself.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":27156,"tokens_out":11136,"duration_ms":121935,"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":[{"comment":"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":"Section 3, Lemma 3.13"},{"comment":"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":"Section 2, Theorem 2.7"},{"comment":"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.","section":"Section 3, Lemma 3.13"}],"minor_comments":[{"comment":"There is a typo: 'A matching of size of size s + 1' repeats 'of size'.","section":"Section 1.1"},{"comment":"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":"Section 3, Lemma 3.5"},{"comment":"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":"Section 3, Lemma 3.7"},{"comment":"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.","section":"Section 2, Theorem 2.7"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The central stability theorem is promising, and the paper's scope is well matched to math.CO. My main concern is that Lemma 3.13 is not a minor gap: its false density inference underpins the trichotomy used in Theorems 1.2 and 1.3. I would encourage the editor to request a revised version with a valid proof of Lemma 3.13, a clarification of Lemma 3.14, and a repair of the application in Theorem 2.7. The paper should not be rejected outright, since the Perron-vector machinery and the general framework appear sound and the gap may be fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth reading, and it is also not ready as written. The covering-number framework—beta', H(F), M(F)—is genuinely new, and the main theorems (1.1–1.4) would be a substantial advance if the proofs hold. The recovery of known results (Cioaba-Desai-Tait, Wang-Hou-Ma, etc.) is a good sanity check, and the new applications to {M_{s+1}, F} and {C_{>=k}, F} are attractive. The Perron-vector stability argument in Theorem 3.3 and the edge-switching comparisons in Section 4 are mostly careful and check out line by line.\n\nThe soft spot is Lemma 3.13, and it is load-bearing. The proof claims that if a component B'' of G[B] has order at least 4, then e(B'') >= |B''|-1 >= (3/4)|B''|, and concludes that the number of such components is O(1). That inference is false: n/8 disjoint P4 components occupy n/2 vertices and contribute (3/8)n excess, which is consistent with the lemma's assumption ex_H(n,F) <= e(H) + r n + O(1) for r = 1/2. So the definition of p as the largest order with infinitely many components is unjustified—p could be 4 or larger—and the trichotomy r in {0, 1/2, 2/3} does not follow. Since Lemma 3.13 is used directly in the proofs of Theorems 1.2 and 1.3 (and via them in several corollaries), the intermediate-density classification currently rests on an unproven structural claim. This is not a cosmetic gap.\n\nA second, smaller issue: Theorem 2.7 applies Corollary 2.6, which assumes a finite degenerate family, to an infinite family defined as all graphs containing every tree of order 2t+2. That is easily repaired by replacing it with the finite set of all trees on 2t+2 vertices, so I would not hold that against the paper beyond a request for clarification.\n\nThe reader's report gave a conditional accept with soundness 7/10; I think the Lemma 3.13 gap makes the conditional verdict too optimistic. But the framework is solid and the gap may be fixable—it needs a real argument bounding the number of components of order >=4, not the density inference used now.\n\nRecommendation: send to peer review, and ask the referee to focus on Lemma 3.13. If the trichotomy can be repaired, this is a strong paper. If not, Theorems 1.2 and 1.3 fall back to being conjectural.","headline":"Novel covering framework and attractive applications, but a false density inference in Lemma 3.13 leaves Theorems 1.2 and 1.3 unproven.","tokens_in":27684,"tokens_out":10221,"would_cite":false,"duration_ms":109326,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C35"],"pacs":[],"model":"deepseek-v4-flash","headline":"Spectral extremal graphs for degenerate families are edge-extremal","keywords":["spectral radius","degenerate graph family","spectral Turán problem","independent covering","extremal graphs","spectral stability","forbidden subgraphs"],"falsifier":"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.","tokens_in":26618,"feed_emoji":"📈","tokens_out":7581,"duration_ms":80126,"temperature":0.7,"pith_summary":"The paper proves a general transfer principle: for a finite degenerate forbidden family F (one containing a bipartite graph) whose Turán number is linear, and whose independent-covering number β′(F) is at least 2, the graphs maximizing spectral radius among F-free n-vertex graphs coincide, for large n, with the edge-extremal graphs built from an auxiliary extremal core. Specifically, any spectral extremal graph has the form T ∨ Q, where T is an extremal graph on β′(F)−1 vertices for the auxiliary family H(F), and Q is an edge-extremal graph on the remaining vertices relative to that skeleton. This resolves the spectral extremal problem for a broad class of families at once, and implies several recent results as corollaries. It also establishes the correlation between edge-extremal and spectral-extremal graphs: under mild sparsity conditions every spectral extremal graph is an ordinary extremal graph.","feed_headline":"Spectral maximizers for degenerate families are edge-extremal","feed_subtitle":"A stability theorem forces every spectrum-maximizing F-free graph into a small, explicit extremal family.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the general spectral extremal theorem and the structural idea behind Lemma 3.13, which classifies the possible surplus terms in ex_H(n,F).","marker":"[3]"},{"why":"Provides the edge-switching lemma (Lemma 3.1) used to show that any deviation from the extremal skeleton strictly increases the spectral radius.","marker":"[34]"},{"why":"Chvátal–Hanson bound on edges in terms of matching number and maximum degree is used to bound ex_H(n,F) in Lemma 4.1 and in the matching-family applications.","marker":"[11]"},{"why":"Determines Ex(n, {M_{s+1}, F}), the edge-extremal structure that Theorem 2.3 converts into a spectral statement.","marker":"[37]"},{"why":"Determines the Turán number of {M_{s+1}, K_{r+1}}, which yields Corollaries 2.4 and 2.5 as applications.","marker":"[1]"},{"why":"Gives bounds on ex(n,T_t) and ex_H(n,F) used in the spectral Erdős–Sós application (Theorem 2.7).","marker":"[9]"},{"why":"Erdős–Gallai bound on graphs without long cycles is used in the proof of Theorem 1.4 for families {C_{≥k}, F}.","marker":"[14]"},{"why":"Provides the Turán number of {C_{≥k}, K_{r+1}}, which underlies the spectral classification in Theorem 2.10.","marker":"[13]"}],"fun_headline_variants":["Spectral stability yields edge-extremal classification","For degenerate graphs, spectral and edge extremal align","Stability forces spectral extremal graphs to be edge-extremal","Spectral and edge extremal coincide for degenerate graphs","Degenerate spectral extremal graphs are edge-extremal"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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).","fun_headline_variants_meta":{"raw":{"variants":["Spectral stability yields edge-extremal classification","For degenerate graphs, spectral and edge extremal align","Stability forces spectral extremal graphs to be edge-extremal","Spectral and edge extremal coincide for degenerate graphs","Degenerate spectral extremal graphs are edge-extremal"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000908,"raw_usage":{"total_tokens":3865,"prompt_tokens":871,"completion_tokens":2994,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":487,"completion_tokens_details":{"reasoning_tokens":2915}},"tokens_in":487,"tokens_out":2994,"duration_ms":25240,"temperature":1.0,"reasoning_tokens":2915,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:00:14.431492+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the edge-switching lemma (Lemma 3.1) used to show that any deviation from the extremal skeleton strictly increases the spectral radius."},{"cited_title":"Chv´atal, D","cited_arxiv_id":null,"evidence_quote":"Chvátal–Hanson bound on edges in terms of matching number and maximum degree is used to bound ex_H(n,F) in Lemma 4.1 and in the matching-family applications."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Determines Ex(n, {M_{s+1}, F}), the edge-extremal structure that Theorem 2.3 converts into a spectral statement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Determines the Turán number of {M_{s+1}, K_{r+1}}, which yields Corollaries 2.4 and 2.5 as applications."},{"cited_title":"Cioab ˘a, D.N","cited_arxiv_id":null,"evidence_quote":"Gives bounds on ex(n,T_t) and ex_H(n,F) used in the spectral Erdős–Sós application (Theorem 2.7)."},{"cited_title":"Erd ˝os, T","cited_arxiv_id":null,"evidence_quote":"Erdős–Gallai bound on graphs without long cycles is used in the proof of Theorem 1.4 for families {C_{≥k}, F}."},{"cited_title":"The number of edges in graphs with bounded clique number and circumference","cited_arxiv_id":"2410.06449","evidence_quote":"Provides the Turán number of {C_{≥k}, K_{r+1}}, which underlies the spectral classification in Theorem 2.10."}],"review_version":1}