{"id":"a6e8ba93-c885-4648-b625-3defdbc2f449","arxiv_id":"2508.07550","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The Brouwer spectral conjecture holds for all connected graphs whose vertex count is at least 4 times the square of the maximum degree; the ordinary-graph case also implies the loop/multigraph case.","lead":"This paper proves a new partial case of the Brouwer conjecture, a 20-year-old open problem on the largest Laplacian eigenvalues of a graph. It shows the conjecture holds for every connected graph whose number of vertices is at least four times the square of its maximum degree, and that a proof for ordinary graphs would automatically cover graphs with loops and parallel edges.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Headline theorem overstates Theorem 3: proof requires connectedness, abstract drops it, and the global size condition does not cover disconnected components.","rationale":"The reader's weakest_assumption points to the eigenvalue-degree bound λ_k ≤ d_k + d_{k+1} from [19]. For Theorem 3, only λ1 ≤ 2d1 is needed, and for simple graphs this follows immediately from Gershgorin's circle theorem on K = D - A (each disk centered at d_i with radius d_i), so that external bound is not the fragile load-bearing step. The interlacing lemma for edge deletion is a standard result (Godsil-Royle Thm 13.6.2) and the tree base case is published. The proof of the connected case is algebraically sound: the case split at k=2d1 works, and each induction step preserves BC. The genuine weakness is the mismatch between the abstract's unqualified 'all graphs' statement and the connectedness hypothesis in Theorem 3. The proof cannot be trivially extended because the global size condition does not constrain individual components. The paper itself discloses other issues (failed Proposition 3, loop convention inconsistencies, typo in Theorem 2 proof), but those do not affect Theorem 3's core argument for connected simple graphs. Therefore the reader's CONDITIONAL verdict is appropriate, though the specific weakest assumption should be revised to the connectedness overstatement.","tokens_in":14112,"tokens_out":18999,"duration_ms":199647,"concrete_test":"Construct the disconnected graph G = P_32 ∪ K_4 (or any graph where n ≥ 4d1^2 but some component fails n_C ≥ 4d1(C)^2) and verify that the proof of Theorem 3 cannot be applied to that component: the first step 'Take a spanning tree' fails for the whole graph, and the component K_4 does not satisfy the connected theorem's size condition. Then check whether the paper contains any separate lemma covering components with n_C < 4d1(C)^2; if none exists, the abstract claim is unsupported. This settles that the overstatement is real (though the connected result may stand).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's advertised central claim—BC for all graphs with n ≥ 4d1^2 (abstract, §1.3)—is stronger than the theorem actually proved. Theorem 3 (Section 5.4) is explicitly for connected graphs, and its proof uses connectedness essentially: it takes a spanning tree H0 ⊂ G and adds back edges one by one, invoking the interlacing lemma for edge addition. For a disconnected G, no spanning tree exists. The natural reduction to components does not follow from the stated hypothesis: the inequality n ≥ 4d1^2 for the whole graph does not imply each component C satisfies n_C ≥ 4d1(C)^2. Example: G = P_32 ∪ K_4 has n=36, d1=3, so 36 ≥ 36; but K_4 has n_C=4 < 36 = 4*3^2. The paper provides no argument for such small components. The body theorem is likely correct, but the abstract's all-graphs statement is unproven. This is a substantive gap in the central claim as presented, not a mere typo.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies Brouwer's conjecture on sums of the largest k Laplacian eigenvalues. Its main theorem (Theorem 3, §5.4) states that every connected graph with n ≥ 4d1^2 satisfies S_k ≤ m + k(k+1)/2 for all k. The proof starts from a spanning tree, uses the known tree case and edge-deletion interlacing, and adds edges back one by one; the two cases k ≥ 2d1 and k ≤ 2d1 are handled via λ1 ≤ 2d1 and n ≤ m+1. The paper also proves sandwich estimates D_k ≤ S_k ≤ 2D_k, extends BC from simple graphs to quivers via rank-one perturbations, and proves a snap-reduction lemma. The abstract, however, omits connectedness and claims the result for all graphs.","tokens_in":14163,"tokens_out":15368,"duration_ms":172708,"significance":"If the body theorem is correct, it is a nontrivial threshold result: Brouwer's conjecture holds for all sufficiently large connected graphs of bounded maximum degree. The interlacing edge-addition scheme is clean, and the proof is self-contained apart from three published ingredients ([14], [19], and the interlacing lemma). The paper is also honest about several speculative directions and includes reproducible code. The main weakness is the gap between the connected theorem and the unqualified abstract/§1.3 claim; until that is fixed, the advertised 'all graphs' statement is unsupported.","major_comments":[{"comment":"The abstract claims that (BC) holds for all graphs with n ≥ 4d1^2, and §1.3 states the same for all quivers, with no connectedness restriction. Theorem 3 is explicitly for connected graphs, and the proof uses connectedness essentially: it takes a spanning tree, and case (ii) invokes n ≤ m+1, which need not hold for a disconnected graph. The global condition also does not imply the same condition on each component: G = P_32 ∪ K_4 has n = 36, d1 = 3, so n ≥ 36, but the K_4 component has n_C = 4 < 36 = 4 d1(K_4)^2. Thus the theorem cannot be applied componentwise, and no other disconnected-case argument is provided. The headline claim must be corrected to the connected statement or supplied with a separate proof.","section":"Abstract and §1.3 vs §5.4, Theorem 3"}],"minor_comments":[{"comment":"In the proof of the quiver upgrade, 'Bk = m + r + n(n+1)/2' should read 'k(k+1)/2'.","section":"§4.2, proof of Theorem 2"},{"comment":"The cycle example is misprinted: 'csc(2n/π)' should likely be csc(π/(2n)), and the inequality '1+2k ≤ k(k+1)/2' is false for k = 1,2. Since the theorem already covers these graphs for n ≥ 16, the example should be rewritten.","section":"§5.5(a)"},{"comment":"The proof of Proposition 3 appears incomplete. It begins 'If G is a quiver with m vertices' even though m is also used for the edge count, and the snap-reduction step acknowledges that m(H) ≥ λ1(H)^2 may fail, which is precisely what the induction would need. Please replace this with the edge-adding induction used in Theorem 3, or delete the proposition.","section":"§6.5, Proposition 3"},{"comment":"Minor wording: 'the µl list is interlaced with the λl list' should be 'the µ list is interlaced with the λ list'.","section":"§5.2"}],"recommendation":"major_revision","confidential_remarks":"The body theorem appears correct, and the main issue is the mismatch between the connected theorem and the unqualified abstract/§1.3 claim. This is fixable by rewording or by adding a component-wise argument. The paper is within scope for math.CO and should not be rejected on this basis."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague, quick take: the real content here is Theorem 3 — for connected graphs with n ≥ 4 d1^2, the Brouwer conjecture holds. The proof is short and, as far as I can check, valid: the spanning-tree edge-addition induction with interlacing, the split at k = 2d1, and the n ≤ m+1 step all work given the cited inputs (the λ_j ≤ d_j + d_{j+1} bound from the author's [19], BC for trees, and the interlacing lemma). The quiver reduction (Theorem 2) is also fine as a simple Hadamard-perturbation observation. So there is a genuine new result here for bounded-degree graphs above a size threshold.\n\nBut the abstract and bullet list overclaim: they say BC holds for all graphs with n ≥ 4 d1^2, while Theorem 3 is proved only for connected graphs, and the proof uses connectivity essentially (spanning tree and n ≤ m+1). The reduction to components does not follow from the global bound. Example: P_32 ∪ K_4 has n = 36 and d1 = 3, so n ≥ 4d1^2, but the K_4 component has 4 < 36 vertices and the paper gives no argument for it. This is a real gap in the advertised claim, even if the connected statement is true.\n\nOther soft spots, in decreasing order. Proposition 3 is stated as a result, but the proof explicitly breaks down at the last line (\"m(H) ≥ λ1(H)^2 does not hold\") — it should be labelled as a conjecture or removed. The quiver-gradient definition is inconsistent for loops: 2.1 says loops count in D, 9.10 defines the gradient to have zero entries for loops, and 9.12 uses nonzero entries. The cycle example asserts 1 + 2k ≤ k(k+1)/2, which is false at k = 1. There is a literal '?' in the Berndsen citation, and Theorem 2's proof says n(n+1)/2 where it means k(k+1)/2. None of these touch the main theorem, but a referee should flag them.\n\nThe load-bearing use of the author's own [19] (λ_j ≤ d_j + d_{j+1}) is worth a careful check, especially because the paper itself reports that an earlier bound was wrong; this one looks credible but is not machine-checked.\n\nWho it's for: spectral graph theorists working on the Brouwer conjecture. They should know about the connected threshold result, but read the theorem statement, not the abstract. I'd send it to peer review: the core theorem deserves a serious referee, and the revision list is clear.","headline":"The connected-graph threshold theorem looks right and is new, but the abstract's 'all graphs' claim is not proven, and several less central parts need cleaning.","tokens_in":14877,"tokens_out":5582,"would_cite":true,"duration_ms":53540,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"Brouwer's conjecture is proved for every connected graph whose vertex count reaches four times the square of its maximum degree.","keywords":["Brouwer conjecture","Kirchhoff Laplacian","Laplacian eigenvalues","sum of largest eigenvalues","quivers","eigenvalue interlacing","degree bounds","spectral graph theory"],"falsifier":"Find a connected graph with $n \\ge 4d_1^2$ whose three largest Kirchhoff eigenvalues sum to more than $m + 6$; that single case would refute the theorem, since $k=3$ is already open. More directly, any quiver with $\\lambda_k > d_k + d_{k+1}$ for some $k$ would break the key inequality on which the threshold rests.","tokens_in":13781,"feed_emoji":"🧮","tokens_out":12824,"duration_ms":116222,"temperature":0.7,"pith_summary":"The paper targets the 20-year-old Brouwer conjecture, which says that the sum $S_k$ of the $k$ largest eigenvalues of the Kirchhoff (graph Laplacian) matrix of a graph is at most the number of edges plus $k(k+1)/2$. The main result proves this bound for every connected graph with $n$ vertices and maximum degree $d_1$ once $n \\ge 4d_1^2$; in other words, all bounded-degree graphs are settled once they are large enough. The proof starts from a spanning tree, where the conjecture is already known, and shows that adding edges one at a time preserves the inequality via eigenvalue interlacing and an eigenvalue-degree bound. The paper also shows that solving the conjecture for simple graphs would automatically solve it for quivers (graphs with loops and multiple edges), with the bound adjusted by a redundancy term.","feed_headline":"Brouwer bound proven for all large bounded-degree graphs","feed_subtitle":"More vertices than four times the squared max degree makes Brouwer's 20-year-old eigenvalue bound provable.","key_machinery":"The proof is carried by two ingredients. First, the interlacing lemma for edge deletion: if $H = G-e$, the eigenvalues $\\mu_j$ of $H$ interlace those $\\lambda_j$ of $G$, so $\\mu_j \\ge \\lambda_{j+1}$, which lets each spectral sum of the larger graph be charged against a smaller-rank spectral sum. Second, the eigenvalue-degree bound $\\lambda_k \\le d_k + d_{k+1}$ for every quiver, proved in the author's earlier work, gives $\\lambda_1 \\le 2d_1$ and fixes the $4d_1^2$ threshold where the two cases in the induction close.","core_discovery":"The central result is Theorem 3: if $G$ is connected and $n \\ge 4d_1^2$, then $S_k = \\sum_{j=1}^k \\lambda_j \\le m + k(k+1)/2 = B_k$ for every $1 \\le k \\le n$, with $\\lambda_1 \\ge \\cdots \\ge \\lambda_n$ the Kirchhoff eigenvalues. The proof fixes a spanning tree $H_0$, which satisfies BC by a known result, and adds the missing edges one at a time. Edge deletion interlaces the spectra, so the sum for the larger graph can be bounded by a one-rank-smaller sum for the smaller graph; the split $k \\ge 2d_1$ and $k \\le 2d_1$ then uses $\\lambda_1 \\le 2d_1$ to close both cases. A second theorem shows the conditional quiver extension: if BC holds for all finite simple graphs, it holds for all quivers wit","pith_inferences":["The constant 4 is an artifact of the coarse bound $\\lambda_1 \\le 2d_1$; any improvement to the spectral-radius bound would lower the threshold and cover denser families under the same induction.","Because the proof needs only a spanning tree, the connectedness hypothesis may be replaceable by a spanning-forest argument; testing that would decide whether the abstract's stronger 'all graphs' statement follows from the same method.","The edge-by-edge induction is constructive: for any graph in the range it produces an explicit order in which edges can be added while preserving the bound, so a computational certificate for large bounded-degree graphs is feasible.","The snap-reduction lemma suggests a dual induction that deletes vertices instead of adding edges, which would become a proof strategy for all graphs once the spectral radius is controlled below $k$."],"forward_implications":["Every connected graph with bounded maximum degree satisfies the Brouwer bound once its vertex count is at least $4d_1^2$; no further structural assumptions are needed.","For a fixed degree bound $d_1$, only graphs with $n < 4d_1^2$ remain open, so the conjecture is reduced to a finite check for each maximum degree.","If the Brouwer conjecture is ever proved for finite simple graphs, the same theorem gives it for all quivers, with the bound $B_k = m + r + k(k+1)/2$ for redundant edges $r$.","Raising the Brouwer threshold $s$ above its current value $2$ would prove the conjecture for every quiver with spectral radius at most $s$ (Corollary 1).","Repeated Barycentric refinement of a triangle-free graph doubles the edge count without raising the maximum degree, so sufficiently refined graphs enter the theorem's range."],"supporting_citations":[{"why":"Supplies the eigenvalue bound $\\lambda_k \\le d_k + d_{k+1}$ for all quivers, which yields $\\lambda_1 \\le 2d_1$ and sets the $4d_1^2$ threshold in Theorem 3.","marker":"[19]"},{"why":"Provides the base case that every tree satisfies the Brouwer bound, from which the spanning-tree induction in Theorem 3 starts.","marker":"[14]"},{"why":"Contains the interlacing theorem (13.6.2) for Kirchhoff spectra after edge deletion, the engine that lets each edge addition preserve the inequality.","marker":"[11]"},{"why":"The source of the Brouwer conjecture and of the standard spectral inequalities used as context throughout the paper.","marker":"[4]"},{"why":"Gives the stronger bound $S_k \\le m + k^2$ that the paper calls the Lew bound and extends to quivers.","marker":"[22]"}],"fun_headline_variants":["Brouwer bound proven for all n ≥ 4Δ²","Eigenvalue sum bound provable for large sparse graphs","Brouwer conjecture holds when n exceeds 4Δ²","Graph spectral bound proven for n ≥ 4 times max degree squared","Brouwer bound proven for graphs with n ≥ 4d_max²"],"cache_read_input_tokens":2816,"weakest_assumption_plain":"The whole proof depends on the published inequality that the $k$-th largest Kirchhoff eigenvalue is at most the sum of the $k$-th and $(k+1)$-st largest vertex degrees; if that bound has a counterexample, the threshold $4d_1^2$ no longer forces the two-case split that closes the induction.","fun_headline_variants_meta":{"raw":{"variants":["Brouwer bound proven for all n ≥ 4Δ²","Eigenvalue sum bound provable for large sparse graphs","Brouwer conjecture holds when n exceeds 4Δ²","Graph spectral bound proven for n ≥ 4 times max degree squared","Brouwer bound proven for graphs with n ≥ 4d_max²"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001168,"raw_usage":{"total_tokens":4624,"prompt_tokens":657,"completion_tokens":3967,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":401,"completion_tokens_details":{"reasoning_tokens":3891}},"tokens_in":401,"tokens_out":3967,"duration_ms":29321,"temperature":1.0,"reasoning_tokens":3891,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T22:05:48.331325+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Find a connected graph with $n \\ge 4d_1^2$ whose three largest Kirchhoff eigenvalues sum to more than $m + 6$; that single case would refute the theorem, since $k=3$ is already open. More directly, any quiver with $\\lambda_k > d_k + d_{k+1}$ for some $k$ would break the key inequality on which the threshold rests.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the eigenvalue bound $\\lambda_k \\le d_k + d_{k+1}$ for all quivers, which yields $\\lambda_1 \\le 2d_1$ and sets the $4d_1^2$ threshold in Theorem 3."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the base case that every tree satisfies the Brouwer bound, from which the spanning-tree induction in Theorem 3 starts."},{"cited_title":"Godsil and G","cited_arxiv_id":null,"evidence_quote":"Contains the interlacing theorem (13.6.2) for Kirchhoff spectra after edge deletion, the engine that lets each edge addition preserve the inequality."},{"cited_title":"Brouwer and W.H","cited_arxiv_id":null,"evidence_quote":"The source of the Brouwer conjecture and of the standard spectral inequalities used as context throughout the paper."}],"review_version":1}