{"id":"938987ad-18f3-407b-a691-73c36a66bf17","arxiv_id":"2607.03388","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Equality holds in Brouwer's Laplacian conjecture for some 1≤k≤n-1 if and only if G is a threshold graph with clique number k+1.","lead":"The paper proves that equality in Brouwer's Laplacian eigenvalue sum bound holds for some k precisely when the graph is a threshold graph of clique number k+1. This finishes the full characterization of extremal graphs after the inequality itself was recently settled.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The central claim (Thm 28) is the equality characterization of Brouwer’s inequality. The logical chain is: (i) Kothari–Tudose projection reduction + equality analysis \to G split (Thm 23); (ii) refined Bai + Berndsen on split graphs \to nested neighborhoods and clique number exactly k+1 (Thms 25–27). Both steps are written out in full; the only residual risk is the usual one of a subtle algebraic slip in a principal-minor or homotopy identity. The concrete determinant check above would catch the most plausible such slip; if it holds, the argument stands. The reader’s weakest-assumption diagnosis is therefore accurate, yet the concern does not rise to a level that warrants changing the ACCEPT verdict. No free parameters, no external data, and no circularity appear. Formal verification is absent, but the pure-math exposition is self-contained and inspectable.","tokens_in":15841,"tokens_out":538,"duration_ms":5149,"concrete_test":"Independently recompute the 3\times3 principal-minor determinant in Lemma 19 under the three sign patterns of a pair (P,G) for generic a c0 with a1; verify that det A is strictly negative whenever the two non-edges and one edge forbidden by the lemma are present. If the determinant can be non-negative for some admissible (a,b,c), the pair-to-split implication fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader correctly flags the projection-to-split reduction (Thm 23 via Lemmas 14–22) as the most delicate step, but the equality-case analysis appears tight: Cauchy–Schwarz forces 1-|Mij|=c|vi-vj|, the ordered partial-sum condition forces c=1/n (or v=0), and the resulting sign pattern Pij=max(Pii,Pjj)-1 or min(Pii,Pjj) yields a pair whose principal 3\times3 minors forbid the two forbidden configurations (Lemmas 19, 21). The maximality definition of r then cleanly produces a clique–independent-set partition. The subsequent split-graph characterization (Thm 25–27) rests on a careful extraction of equality from Bai’s homotopy (linearly ordered neighborhoods) plus Berndsen’s gap function, both of which are classical and appear correctly applied. No internal inconsistency or missing case is visible.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper confirms the full Brouwer Laplacian conjecture of Li and Guo: for a graph G on n vertices and 1 ≤ k ≤ n-1, the sum of the k largest Laplacian eigenvalues satisfies sk(G) ≤ e(G) + binom(k+1,2), with equality if and only if G is a threshold graph of clique number k+1 (equivalently G ≅ Gk,r,s). The argument first extracts equality conditions from the Kothari–Tudose orthogonal-projection reduction (Lemmas 13–17), shows that any equality-attaining pair (P,G) forces G to be split (Theorem 23 via principal-minor contradictions in Lemmas 19–22), then improves Bai’s lemma for split graphs to obtain nested neighborhoods (Lemma 24) and characterises the extremal split graphs via Berndsen’s gap function (Theorems 25–27). The inequality itself is taken from Kothari–Tudose; the contribution is the equality characterisation.","tokens_in":16018,"tokens_out":840,"duration_ms":6383,"significance":"Brouwer’s conjecture is a central problem in spectral graph theory; its full equality characterisation has been open since Li–Guo (2022). Completing the characterisation after the inequality was settled is a natural and valuable contribution. The paper gives a clean two-step reduction (projection equality \to split \to nested-neighbourhood threshold graphs) that re-uses classical tools (Bai homotopy, Berndsen gap, Grone–Merris–Bai) in a transparent way. The principal-minor arguments that force the split partition and the refined equality extraction from Bai are technically solid and of independent interest for other Laplacian-sum problems.","major_comments":[],"minor_comments":[{"comment":"Section 3.2, Lemma 15: the case distinction “v = 0 versus existence of r0 with vr0 > 0 ≥ vr0+1” is correct but terse; a one-sentence reminder that the non-decreasing ordering of vi together with sum vi = 0 forces the sign change (or the zero vector) would improve readability.","section":"Section 3.2, Lemma 15"},{"comment":"Definition 2 / Theorem 3: the family Gk,r,s is introduced by reference to Chen–Zi; a short self-contained sentence that these are precisely the threshold graphs of clique number k+1 with nested neighbourhoods would make the paper more self-contained.","section":"Definition 2"},{"comment":"Lemma 24: the extraction of the linear-order condition from Bai’s homotopy (especially the implication aij = 0 ⇒ vji = 0 and the subsequent contradiction for incomparable neighbourhoods) is dense; a brief schematic of the sign pattern of V would help the reader follow the argument.","section":"Lemma 24"},{"comment":"Throughout: a few typographical slips (e.g., “We remains to prove”, occasional missing spaces around “=”) should be cleaned in the final version.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a clean equality-case companion to the already-accepted Kothari–Tudose proof. Novelty is appropriately scoped; the technical core (projection-to-split reduction and refined Bai equality) is original and carefully executed. Suitable for a solid combinatorics or linear-algebra journal."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This paper finishes the equality side of Brouwer’s Laplacian conjecture: for 1 ≤ k ≤ n-1, sk(G) = e(G) + binom(k+1,2) if and only if G is a threshold graph of clique number k+1 (i.e., one of the Gk,r,s graphs). The inequality itself is already due to Kothari–Tudose; the new content is the if-and-only-if statement that Li–Guo had formulated as the “full” conjecture.\n\nWhat they do well is extract equality conditions carefully from the projection reduction. They force the sign pattern on the projection matrix P, show that any equality-attaining pair (P,G) must be a split graph (via 3\times3 principal-minor contradictions that rule out the two forbidden neighborhood configurations), then improve Bai’s lemma for split graphs so that equality forces nested neighborhoods and therefore a threshold graph of the right clique number. The Berndsen gap-function analysis and the complement relation are used cleanly. The logical chain is written out in full and can be checked line-by-line; there are no free parameters or circular definitions.\n\nThe softest step is exactly the one the reader flagged: the reduction that equality forces a split graph (Theorem 23 via Lemmas 14–22). It rests on Cauchy–Schwarz equality plus the ordered partial-sum condition forcing c = 1/n (or v = 0), which produces the rigid sign pattern for the off-diagonal entries of P. The subsequent principal-minor arguments look correct on a careful reading, and the maximality definition of r then yields the clique–independent-set partition without missing cases. The later split-graph characterization is classical and appears correctly applied. Residual risk is the usual one for a long pure-math argument—a subtle gap in a minor or homotopy step—but nothing jumps out as broken.\n\nThis is for spectral-graph-theory people who care about Laplacian partial sums and extremal characterizations. It organizes the equality cases that the literature has been circling for a decade. I would send it to referees; the result is solid enough and the write-up transparent enough to deserve a careful check rather than a desk reject. Worth citing if you work on these bounds.","headline":"Clean equality characterization of Brouwer after Kothari–Tudose; the projection-to-split step is the only delicate piece and it looks tight.","tokens_in":16694,"tokens_out":578,"would_cite":true,"duration_ms":5044,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","15A42"],"pacs":[],"model":"grok-4.5","headline":"Equality in Brouwer's Laplacian bound holds exactly for threshold graphs of clique number k+1.","keywords":["Brouwer's conjecture","Laplacian eigenvalues","sum of eigenvalues","threshold graphs","split graphs","equality characterization","projection method"],"falsifier":"Exhibit a non-split graph (or a split graph that is not threshold of clique number k+1) on which the sum of the k largest Laplacian eigenvalues exactly equals the number of edges plus binom(k+1,2) for some 1 ≤ k ≤ n-1.","tokens_in":16698,"feed_emoji":"📊","tokens_out":911,"duration_ms":6781,"temperature":0.7,"pith_summary":"Brouwer's conjecture bounds the sum of the k largest Laplacian eigenvalues of a graph by the number of edges plus a triangular number. The inequality itself was already proved; this paper settles when equality can occur. For any k between 1 and n-1, the bound is tight if and only if the graph is a threshold graph whose largest clique has size exactly k+1. The argument first forces any equality-attaining graph to be split by examining the orthogonal projection onto the top-k eigenspace, then characterises the equality case among split graphs by showing that neighbourhoods of the independent-set vertices must be nested. The result therefore supplies a complete, explicit list of the extremal graphs.","feed_headline":"Equality in Brouwer bound only for threshold graphs","feed_subtitle":"The sum of the k largest Laplacian eigenvalues meets the edge-plus-triangle bound exactly when the graph is threshold of clique number k+1.","key_machinery":"The projection reduction of Kothari–Tudose: an orthogonal projection P of rank k orthogonal to the all-ones vector turns equality into sign-and-order constraints on the entries of P; those constraints force the graph to be split, after which an improved form of Bai's lemma characterises the nested-neighbourhood condition that defines threshold graphs.","core_discovery":"For every graph G on n vertices and every integer k with 1 ≤ k ≤ n-1, the sum of the k largest Laplacian eigenvalues equals e(G) + binom(k+1,2) if and only if G is a threshold graph of clique number k+1 (equivalently, G belongs to the family G_{k,r,s} for some r ≥ 1 and s ≥ 0).","pith_inferences":["The nested-neighbourhood condition that appears in the equality case is exactly the definition of a Ferrers diagram; the same combinatorial object may therefore control equality cases for related spectral majorisation inequalities.","Because the projection argument never uses more than the positive-semidefinite property and the all-ones kernel, the same technique is available for other matrix pencils whose Rayleigh quotients admit an edge-sum representation.","Once the extremal graphs are known, one can compute the precise spectral gap sk(G) - Bk(G) for every non-extremal graph by measuring how far its bipartite adjacency matrix departs from a Ferrers shape."],"forward_implications":["The only graphs that attain the Brouwer bound for a given k are completely classified: they are precisely the threshold graphs with clique number k+1.","For every split graph that is not of this form, the inequality is strict for every k.","The same characterisation recovers the already-known equality cases for trees, unicyclic graphs and other previously settled families as special cases of threshold graphs.","The complement relation for Laplacian sums immediately yields the dual characterisation for the complementary range of k."],"fun_headline_variants":["Equality in Brouwer bound only for threshold graphs of clique number k+1","Laplacian sum equals bound iff threshold graph with clique number k+1","Brouwer equality holds precisely for threshold graphs of clique k+1","Exact Laplacian bound met only by threshold graphs with ω=k+1","Full equality case: threshold graphs of clique number k+1"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The claim that every equality-attaining pair of projection and graph must produce a split graph rests on the sign and ordering constraints extracted from the Cauchy–Schwarz and cut-sum equalities inside the projection framework.","fun_headline_variants_meta":{"raw":{"variants":["Equality in Brouwer bound only for threshold graphs of clique number k+1","Laplacian sum equals bound iff threshold graph with clique number k+1","Brouwer equality holds precisely for threshold graphs of clique k+1","Exact Laplacian bound met only by threshold graphs with ω=k+1","Full equality case: threshold graphs of clique number k+1"]},"model":"grok-4.5","effort":"low","cost_usd":0.008794,"raw_usage":{"total_tokens":1997,"prompt_tokens":701,"num_sources_used":0,"completion_tokens":97,"cost_in_usd_ticks":87940000,"prompt_tokens_details":{"text_tokens":701,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":1199,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":701,"tokens_out":97,"duration_ms":8067,"temperature":1.0,"reasoning_tokens":1199,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T02:50:32.200198+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a non-split graph (or a split graph that is not threshold of clique number k+1) on which the sum of the k largest Laplacian eigenvalues exactly equals the number of edges plus binom(k+1,2) for some 1 ≤ k ≤ n-1.","supporting_citations":[],"review_version":1}