{"id":"de6b2cd4-68fa-44a6-8620-39b0fe7cd2aa","arxiv_id":"2607.17293","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Equality in Brouwer's Laplacian inequality holds exactly for threshold graphs with clique number k+1.","lead":"This paper proves the equality case of Brouwer's conjecture for Laplacian eigenvalues: the sum of the k largest Laplacian eigenvalues equals the edge count plus k(k+1)/2 exactly when the graph is a threshold graph with clique number k+1. It completes a two-decade-old conjecture in spectral graph theory by giving the precise structural condition for when the bound is tight.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Equality characterization depends on Kothari–Tudose Lemma 2.2, which is neither proved nor independently verified; a failure would invalidate the necessity proof.","rationale":"Agree with the reader: the weakest assumption is the reliance on [15, Lemma 5.5]. The internal proof of Lemma 2.3 is correct assuming Lemma 2.2; the Cauchy–Schwarz and Lagrange steps are valid, and the equality analysis (α=1/n) is sound. Lemma 2.4 is also sound; the only blemish is a typo in equation (15) where the sets N and \\bar{N} are interchanged (the sums should be over \\bar{N}), but the intended contradiction is clear and does not affect the result. The derivation of G=Γ(P) from equality in the chain (16) is straightforward. Consequently, the central claim is conditionally established and the dependency on Lemma 2.2 is a standard, though nontrivial, citation. No change to the reader's ACCEPT verdict is warranted; if one wanted extra rigor, the paper could include a proof of Lemma 2.2 or a reference to a peer-reviewed version.","tokens_in":6819,"tokens_out":21498,"duration_ms":167702,"concrete_test":"Verify Lemma 2.2 independently. Either (a) derive the inequality ∥v∥^2 ≤ Σ_{i<j}(1-|M_ij|)|v_i-v_j| from the definition of the orthogonal projection P with P1_n=0, or (b) perform an exhaustive search over all such projections for n≤6, all ranks k, computing M and v and checking the inequality. A counterexample would disprove Lemma 2.3's equality condition (6); a proof would remove the only substantial concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 2.2 (cited as [15, Lemma 5.5]) is the single load-bearing external tool. In Lemma 2.3, it is used to obtain inequality (10), which combines with identity (11) to show the RHS of (7) is nonnegative. The equality case of Lemma 2.3 then forces equality in Lemma 2.2 and in the Cauchy–Schwarz step, yielding condition (6). Theorem 1.3's necessity proof uses (6) to infer G=Γ(P) and, via Lemma 2.4, that G is threshold. If Lemma 2.2 is false, (6) is unjustified and the proof collapses. The paper gives no proof of Lemma 2.2 and [15] is a very recent arXiv preprint; no independent verification is provided. The other dependencies (Li–Guo sufficiency and Chen–Zi clique-number fact) are less critical. This is an external dependency rather than an internal flaw, but it is the weakest point of the chain.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper characterizes the equality case in Brouwer's inequality for Laplacian eigenvalues. The main result (Theorem 1.3) states that for every n-vertex graph G and every k=1,...,n-1, S_k(G)=m+binom(k+1,2) holds if and only if G is a threshold graph with clique number k+1. The proof uses the projection method introduced by Kothari and Tudose in their recent proof of Brouwer's conjecture. After introducing the projection P, the paper proves Lemma 2.3, a sharpened projection inequality with an explicit equality condition, and Lemma 2.4, which shows that any projection satisfying that equality condition defines a threshold graph Γ(P). Applying these to the top-k Laplacian eigenspace projection and using known sufficiency results yields the characterization.","tokens_in":7072,"tokens_out":16988,"duration_ms":134846,"significance":"If correct and once the cited proof of Brouwer's inequality is fully established, this settles the full Brouwer conjecture proposed by Li and Guo. The novelty lies in the equality analysis: Lemma 2.3 converts the global inequality into a rigid structural condition, and Lemma 2.4's induction is elegant and appears sound. The paper is transparent about its dependencies, including the recent proof by Kothari and Tudose and the concurrent work shared by Zhang's group. The proof is not machine-checked, but the reasoning is well-structured and the algebraic steps in Lemmas 2.3 and 2.4 are verifiable. The result is significant and likely to be influential.","major_comments":[{"comment":"The necessity proof of Theorem 1.3 rests on Lemma 2.2 ([15, Lemma 5.5]), which is used to obtain inequality (10) and, in the equality case, condition (6). Lemma 2.4 then relies on (6) to conclude that Γ(P) is threshold. If Lemma 2.2 were false, the proof of Lemma 2.3 and hence the main theorem would collapse. Since [15] is a recent unreviewed arXiv preprint and no proof or independent verification is provided in this manuscript, this is a load-bearing external dependency. Please add a proof of Lemma 2.2 (and ideally Lemma 2.1, or at least a concise verification) in an appendix, or otherwise make the manuscript self-contained. Alternatively, explicitly state that the characterization is conditional on [15] and cite a published/refereed version if one becomes available.","section":"Section 2, Lemmas 2.1 and 2.2 (cited from [15])"}],"minor_comments":[{"comment":"The displayed sums use the symbol N in all three places, but the derivation requires the sums to be over the complementary set \\bar N (the non-neighbors of vertex n). As written with the authors' definition of N (the neighbors), the equalities are false. Please correct the notation.","section":"Lemma 2.4, Case 1, equations before (15) and in (15)"},{"comment":"The identity S_k(G)-m = ∑_{E} M_{ij} is taken from [15, Theorem 3.1] but not proved. This is a short trace computation; including a one-line derivation would make the paper more self-contained.","section":"Section 2, proof of Theorem 1.3, Eq. (16)"},{"comment":"The phrase 'by the same argument as in Case 1' should read 'by the induction hypothesis', since the isolated-vertex case is immediate once Γ(P') is known to be threshold.","section":"Lemma 2.4, Case 2"},{"comment":"The abstract and Conjecture 1.1 state k=1,...,n, while Theorem 1.3 states k=1,...,n-1. Please clarify that equality for k=n is impossible or that this is the standard range for the full conjecture.","section":"Abstract and Theorem 1.3"},{"comment":"The statement that GPT-5.5 Pro was used to simplify the proof of Lemma 2.4 may need to be adjusted to the journal's policy on AI assistance. Please ensure the description is sufficient and compliant.","section":"Declaration of AI Use"}],"recommendation":"major_revision","confidential_remarks":"The paper is mathematically strong and the equality characterization is likely correct, but the dependence on Lemmas 2.1 and 2.2 from [15] is a real risk because that source is a very recent unreviewed preprint. The authors should either prove the load-bearing lemma or make the conditional nature of the result explicit. The note also reveals a concurrent paper [4] with overlapping Lemma 2.3; the editor may want to assess novelty relative to [4] before accepting."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi,\n\nQuick take: this paper settles the equality case for Brouwer's Laplacian inequality, and it does it cleanly. The statement is exactly the natural one — equality iff threshold graph with clique number k+1. The sufficiency was already known from Li–Guo; the new content is necessity.\n\nThe proof is short. It uses Kothari–Tudose's projection method. The genuinely new piece is Lemma 2.4, an induction that starts from condition (6) and forces the projected graph to be threshold. I checked the algebra in Case 1 and it works, though the arXiv text has a few set-notation typos: in the last-row identity the sums should be over the non-neighbor set, not the neighbor set. The printed math is fine.\n\nWhat's good: the paper is transparent about what it's using. It cites the two Kothari–Tudose lemmas explicitly, notes that Lemma 2.3 overlaps with Lemma 15 of concurrent work [4], and declares AI-assisted simplification of the Lemma 2.4 proof. That's the right way to write a follow-up note.\n\nThe soft spot is real but narrow. Lemma 2.2 (Kothari–Tudose's inequality between the norm of v and the weighted sum) is used without proof. It's the load-bearing external tool: equality in Lemma 2.3 forces equality in Lemma 2.2, which gives condition (6). If Lemma 2.2 is wrong, the necessity proof collapses. Kothari–Tudose is a recent arXiv preprint, so no independent verification yet. That's a dependency, not an internal flaw — Brouwer's inequality itself is now considered proved by that preprint, so relying on it for a follow-up is reasonable. But a referee should actually check Lemma 5.5 of [15], or at least confirm the Kothari–Tudose paper has passed scrutiny.\n\nThe result also leans on the Li–Guo sufficiency and the Chen–Zi clique-number fact. Those are published, so less concerning.\n\nOverall it's a solid, honest note. The main theorem is new and the proof is convincing given the external lemmas. I'd send it to peer review. The referee's main job is to verify Lemma 2.2 and the equality-chain step that turns (8)–(9) into (6). If that holds up, this is ready to publish.\n\nFor a reading group, it's a good example of a clean equality-case argument. I'd cite it if I write about Laplacian sums.\n\nCheers.","headline":"Clean equality-case proof that completes Brouwer's conjecture; the only real risk is an external lemma from the Kothari–Tudose preprint.","tokens_in":7532,"tokens_out":5926,"would_cite":true,"duration_ms":42412,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Equality in Brouwer's Laplacian inequality occurs if and only if the graph is a threshold graph with clique number k+1, the authors prove, settling the full conjecture.","keywords":["Brouwer's conjecture","Laplacian eigenvalues","sum of largest Laplacian eigenvalues","equality case","threshold graphs","clique number","projection method","spectral graph theory"],"falsifier":"A single graph G and a single k for which S_k(G) = |E(G)| + binom(k+1,2) but G is not a threshold graph with clique number k+1 would falsify the theorem; a finite exhaustive search over all graphs on, say, n <= 7 vertices would settle the matter, since the theorem claims there are no exceptions.","tokens_in":6723,"feed_emoji":"📐","tokens_out":6119,"duration_ms":57485,"temperature":0.7,"pith_summary":"This paper identifies exactly which graphs make Brouwer's inequality an equality. The claim is that for any graph and any k, the sum of the k largest Laplacian eigenvalues equals the number of edges plus the k+1 choose 2 term precisely when the graph is a threshold graph whose clique number is k+1. Because the inequality side has already been confirmed, this equality characterization completes the full version of Brouwer's conjecture. The proof works by projecting onto the top-k Laplacian eigenspace and showing that equality forces the edge structure to match the projection's sign pattern, which is then proved to be threshold. A sympathetic reader should care because it turns a numerical spectral bound into an exact structural classification with no exceptional graphs.","feed_headline":"Top-k Laplacian sum hits its bound only on threshold graphs","feed_subtitle":"Only threshold graphs with clique number k+1 saturate the bound, completing Brouwer's equality conjecture.","key_machinery":"The central object is the orthogonal projection P onto the top-k Laplacian eigenspace, together with the associated matrix M whose off-diagonal entries M_ij = P_ii + P_jj - 2P_ij - 1 lie in [-1,1]; the sign of M_ij records whether an edge is forced by the projection. Two lemmas about P form the load-bearing machinery: a sharpened inequality bounding the sum of the positive parts of the M_ij by k(k+1), and the consequence that its equality case forces the identity 1 - |M_ij| = |P_ii - P_jj| for all pairs. A further lemma shows this identity makes the graph Gamma(P), defined by M_ij > 0, a threshold graph — that is, a graph built by repeatedly adding either an isolated or a dominating vertex.","core_discovery":"Theorem 1.3 states that a graph G satisfies S_k(G) = |E(G)| + binom(k+1,2) if and only if G is a threshold graph with clique number k+1. The paper's contribution is the necessity direction: if the equality holds, then G must be threshold. The argument restricts the Laplacian to the subspace orthogonal to the all-ones vector and lets P be the orthogonal projection onto the span of the top k eigenvectors. A matrix M is introduced with off-diagonal entries M_ij = P_ii + P_jj - 2P_ij - 1; the left side of the equality minus the number of edges equals the sum of M_ij over edges. Equality forces M_ij > 0 on every edge and M_ij < 0 on every non-edge, so G is exactly the graph Gamma(P) whose edges a","pith_inferences":["Editorial inference: the same projection-plus-sign-pattern argument may characterize equality in other Laplacian sum inequalities, such as the Grone–Merris–Bai majorization, where threshold graphs already appear as extremal cases; a unified proof of equality cases might be possible.","Editorial inference: because equality forces G = Gamma(P), the ordering of the diagonal entries P_ii may determine a vertex ordering that yields a linear-time algorithm for recognizing equality graphs directly from a Laplacian eigenvector basis.","Editorial inference: the result suggests that Brouwer's bound is tight only in the threshold-graph region; graphs far from being threshold should have slack bounded away from zero, which could support an approximate or stable version of the inequality."],"forward_implications":["If Theorem 1.3 is correct, the full Brouwer's conjecture is settled: the inequality holds for every graph, and the equality cases are precisely the threshold graphs of clique number k+1.","The equality condition depends on k only through the clique number: a graph can attain the bound for a given k only if its clique number is exactly k+1.","Equality forces the graph to be threshold, so any graph containing an induced P4, C4, or 2K2 — the minimal obstructions to being threshold — can never saturate the bound.","The proof shows the extremal graph G must coincide with the sign-pattern graph Gamma(P) of the projection, giving an eigenvalue-free structural criterion for equality."],"fun_headline_variants":["Equality in Brouwer's bound occurs only for threshold graphs","Threshold graphs are the unique saturators of Brouwer's inequality","Laplacian sum equality forces threshold structure","Only threshold graphs hit the Laplacian sum ceiling"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The proof relies, without re-proving, on two lemmas from the recently confirmed proof of Brouwer's inequality — in particular the inequality that bounds the squared norm of a certain vector by a weighted sum of absolute differences — so if that lemma cannot be reproduced, the equality characterization collapses.","fun_headline_variants_meta":{"raw":{"variants":["Equality in Brouwer's bound occurs only for threshold graphs","Threshold graphs are the unique saturators of Brouwer's inequality","Laplacian sum equality forces threshold structure","Only threshold graphs hit the Laplacian sum ceiling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000513,"raw_usage":{"total_tokens":2364,"prompt_tokens":810,"completion_tokens":1554,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":554,"completion_tokens_details":{"reasoning_tokens":1488}},"tokens_in":554,"tokens_out":1554,"duration_ms":9641,"temperature":1.0,"reasoning_tokens":1488,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T18:27:21.517634+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A single graph G and a single k for which S_k(G) = |E(G)| + binom(k+1,2) but G is not a threshold graph with clique number k+1 would falsify the theorem; a finite exhaustive search over all graphs on, say, n <= 7 vertices would settle the matter, since the theorem claims there are no exceptions.","supporting_citations":[],"review_version":1}