{"id":"87f5ed0f-30d5-4817-8ca8-1bcd61af75ea","arxiv_id":"2607.23583","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Equality in the Grone–Merris inequality holds exactly for two families obtained by deleting edges from the first dominating block or adding edges inside the first isolated block of a threshold graph, with explicit ranges for k.","lead":"The paper pins down exactly when equality holds in the Grone–Merris bound on Laplacian eigenvalues: only for two explicit families built by editing one terminal block of a threshold graph. It closes a natural open question left after Bai’s proof and the recent Brouwer equality characterization.","discovery_kind":"extension","skeptic_critique":{"model":"moonshotai/kimi-k3","headline":"Theorem 6.1’s “exactly one” exclusivity is false: complete graphs satisfy both Type I and Type II at k=n−1, although the inclusive two-family characterization may remain correct.","rationale":"The reader identified dependence on the external split-graph equality analysis and the authors’ Brouwer equality characterization as the main soft spot. Those are genuine dependencies, but the more immediate internal problem is the quantifier “exactly one” in Theorem 6.1. The reduction establishes existence of a representation from an admissible r0, not uniqueness across all admissible r0. The K4 example satisfies both displayed bounds and both structural constructions, so the theorem’s exclusivity assertion is incorrect as written.\n\nThis is a narrow and readily correctable issue: replacing “exactly one” with inclusive “one of” aligns the statement with what the proof appears to establish. If uniqueness is intended as part of the classification, the authors need a new disjointness argument, and the counterexample shows that the current families are not disjoint. Because the explicit main theorem contains a false assertion but the underlying inclusive characterization may survive, CONDITIONAL is more appropriate than unconditional ACCEPT.","tokens_in":14907,"tokens_out":11278,"duration_ms":305850,"concrete_test":"Evaluate Theorem 6.1 on G=K4, k=3. Verify Type I with U1=V and F=K4, giving 0≤3≤min{3,c(\\bar K4)−1}=3. Independently verify Type II with \\bar K4 having B1={v}, A1=V\\{v}, r0=3, |B1|=1, Δ(F)=0, c(F)=1, giving 3≤3≤3. If both checks pass—as they do—the claimed exclusivity fails and must be removed or reproved under added restrictions.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The necessity proof chooses an integer r0 supplied existentially by Proposition 5.2 and then separates q<r0 (Case A/Type I) from q≥r0 (Case B/Type II). That dichotomy is exclusive only for the chosen r0. The proof never shows that the same pair (G,k) cannot satisfy the conditions through two different admissible values of r0, yielding both terminal-block representations.\n\nA direct counterexample is G=K4, k=3. For Type I, take H=K4 with creation sequence U1=V, F=K4. Then sum_{i≥2}|Ui|=0, δ(F)=3, and c(\\bar F)−1=3, so (8) gives k=3. For Type II, take the same H=K4. Its complement is edgeless, with creation sequence B1={v}, A1=V\\{v}; hence r0=3, |B1|=1, and F on B1 has Δ(F)=0 and c(F)=1. Then (9) gives 3≤k≤3. Thus (K4,3) belongs to both families. Spectrally, this corresponds to admissible r0=4 with q=0 in the first representation and r0=3 with q=3 in the second.\n\nTherefore Theorem 6.1 is false as written if “exactly one” is part of the claim. The likely repair is to state “one of” / “at least one of,” or else impose a canonical r0 or additional non-redundancy conditions and prove disjointness. This does not by itself overturn the inclusive equality classification.","agreement_with_reader":"disagree"},"referee_report":{"model":"moonshotai/kimi-k3","summary":"The paper determines the equality cases of the Grone–Merris–Bai inequality ∑_{i≤k} λ_i(G) ≤ ∑_{i≤k} d*_i(G). Following the Kothari–Tudose proof architecture, the authors unwind each inequality in the chain (via Lemma 5.1 and Proposition 5.2) into five explicit conditions involving the threshold parameter r_0, the projection Q_{r_0}, and the associated split graph H. They then analyze equality in the split-graph trace inequality (Theorem 4.1, two cases q < r_0 and q ≥ r_0), using a self-contained spectral description of threshold graphs (Proposition 3.1) and the Brouwer equality characterization from the authors' companion paper [3]. The main result, Theorem 6.1, asserts that equality holds iff (G,k) belongs to \"exactly one\" of two families: Type I (edges deleted inside the initial dominating block U_1 of a threshold graph, with k in the range (8)) and Type II (edges added inside the initial isolated block B_1, with k in the range (9)). Necessity and sufficiency are both argued in detail, with explicit spectral and degree computations.","tokens_in":15236,"tokens_out":6499,"duration_ms":218154,"significance":"If correct, this closes a natural open problem left by Bai's theorem and the recent proof of Brouwer's conjecture: a complete combinatorial catalogue of the pairs (G,k) where the GM bound is tight. The two families are explicit and the membership conditions (8)–(9) are checkable in elementary terms (δ(F), Δ(F), component counts). The derivation is not circular: GM equality is reduced to external theorems (Bai; the Kothari–Tudose trace inequality; the Brouwer equality cases of [3]) plus fresh spectral analysis of terminal-block perturbations, and Proposition 3.1 is proved directly in the paper. The sufficiency section re-verifies all five conditions of Proposition 5.2 rather than appealing to symmetry, which adds confidence. The result is a fitting capstone to this line of work and should be of interest to the spectral graph theory community.","major_comments":[{"comment":"The phrase \"belongs to exactly one of the following two families\" is false: the two families overlap. Counterexample: G = K_4, k = 3 (equality holds: both sides equal 12). Type I: take H = K_4 with creation sequence U_1 = V (m = 1, D_1 empty); then ∑_{i≥2}|U_i| = 0, F = K_4, δ(F) = 3, c(F̄)−1 = 3, so (8) gives 0 ≤ k ≤ 3. Type II: take H = K_4, whose complement is edgeless with creation sequence B_1 = {v}, A_1 = V\\{v}; then r_0 = 3, |B_1| = 1, F on B_1 has Δ(F) = 0 and c(F) = 1, so (9) gives 3 ≤ k ≤ 3. Thus (K_4, 3) belongs to both. The source is visible in the proof: Proposition 5.2 supplies r_0 only existentially, and the Case A/Case B dichotomy is exclusive only for a fixed r_0. For K_4 both r_0 = 4 (giving q = 0 < r_0, Type I) and r_0 = 3 (giving q = 3 ≥ r_0, Type II) are admissible, and the proof never rules out two admissible values of r_0 yielding both representations. The inclusiv","section":"§6.1, Theorem 6.1"}],"minor_comments":[{"comment":"The claim \"u ∈ K\\U_1: d_G(u) ≥ r_0 (since ... adjacent to at least D_1 ≠ ∅ in S)\" uses D_1 ≠ ∅. By the creation-sequence convention D_1 is nonempty whenever m ≥ 2, and K\\U_1 = ∅ when m = 1, so the argument is correct, but a half-sentence making this case split explicit would help the reader.","section":"§6.2, Case A degree platform"},{"comment":"The complement of H is denoted \"H\" in the text (\"H(the complement of H) is a threshold graph\"; \"a threshold graph H whose complement H is a threshold graph\"). Presumably H̄ is intended and the bar was lost in typesetting; please check the rendered manuscript.","section":"§4, Theorem 4.1 Case 2; §6.1, Type II"},{"comment":"The closing assertion that the listed eigenvectors \"span R^V\" would benefit from a one-line dimension count (Type I: ∑(|D_i|−1); Type II: ∑(|U_i|−1); Types III–IV: m and m−1; plus 1). Also worth noting explicitly that the eigenvalue coincidences between types (e.g., Type I on D_h and Type III at h share ∑_{j>h}|U_j|) are consistent, since Remark 3.2 relies on the resulting eigenspace decompositions.","section":"§3, Proposition 3.1"},{"comment":"The deduction of ⌈λ_{k+1}⌉ ≤ r_0 ≤ ⌊λ_k⌋ is correct but compressed; one sentence noting that A_r is constant for r ≤ λ_k and nondecreasing (eventually strictly) for r > λ_k would suffice.","section":"§5, Proposition 5.2(i)"},{"comment":"The Brouwer equality characterization [3] is load-bearing (it forces H to be threshold in both cases of Theorem 4.1) and is currently an arXiv preprint from the same author group. This is legitimate, but the paper would be strengthened by a brief remark on the status of [3] and on precisely which statement is imported.","section":"§2.3, Theorem 2.3"},{"comment":"Typographical: \"the all-one matrix of of appropriate size\" (§1, duplicated \"of\"); Theorem 1.1 displays \"λ_1 ≥ . . . λ_n\" (missing ≥); reference [4] spells \"Chv'atal\"; several spacing artifacts such as \"d H (v)\" and \"λ 1\" appear throughout.","section":"General"}],"recommendation":"minor_revision","confidential_remarks":"The mathematical spine depends on two very recent arXiv preprints: Kothari–Tudose [6] (the split-graph trace inequality, whose equality analysis the authors re-prove in §4, so this dependence is well handled) and the authors' own companion preprint [3] (Theorem 2.3, the Brouwer equality cases), which is used as a black box at a load-bearing point. The editor may wish to confirm the status of [3]. The K_4 counterexample to the \"exactly one\" clause is a statement-level slip rather than a gap in the argument; the underlying classification looks correct and the fix should be a matter of rewording plus a short remark."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The real news is a complete combinatorial list of pairs (G,k) where Grone–Merris is tight: two terminal-block edits of threshold graphs, with explicit windows on k. That was open after Bai and after the Brouwer equality paper. The reduction through the split-graph trace inequality plus the five conditions in Prop. 5.2 is the right spine, and the spectral platforms for the two types are written carefully enough that a specialist can check them.\n\nWhat they do well: they unwind the Kothari–Tudose chain instead of inventing a parallel argument, they give the Laplacian eigenspaces of threshold graphs in usable form, and necessity/sufficiency are both there. Dependence on their own Brouwer equality result and on the trace-equality cases is load-bearing but not circular; it is sequential use of prior theorems.\n\nSoft spot, real but local: Theorem 6.1 claims the pair belongs to “exactly one” of the two families. That is false. Complete graphs sit in both (e.g. K4 at k=3: Type I with empty later U-blocks and F complete; Type II with |B1|=1). The case split is exclusive only for a fixed r0, not across admissible r0’s. Repair is wording—“one of” / “at least one of”—or a canonical r0. I do not see this breaking the inclusive classification or the five-condition reduction.\n\nMinor condensation in some eigenvector-support and Rayleigh steps is the usual cost of a long spectral argument; nothing looked load-bearing-wrong on a full read. Citations are appropriate; no free parameters or data issues.\n\nThis is for people who already care about Laplacian majorization and threshold graphs. Worth a serious referee. I would send it to peer review and would bring it to a spectral-graph reading group after the exclusivity fix is noted. Engage if that is your lane; skip if you only need the inequality itself.","headline":"Clean equality-case classification for Grone–Merris; the “exactly one of two families” wording is wrong but the inclusive description looks right and fixable.","tokens_in":16450,"tokens_out":506,"would_cite":true,"duration_ms":16229,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C75","15A42"],"pacs":[],"model":"grok-4.5","headline":"Equality in the Grone–Merris–Bai bound holds exactly for two surgical modifications of threshold graphs.","keywords":["Grone–Merris inequality","Laplacian eigenvalues","conjugate degree sequence","threshold graphs","equality cases","split-graph trace inequality","Brouwer conjecture"],"falsifier":"Exhibit a concrete graph G and integer k that attain equality in the Grone–Merris sum but are not obtainable by either of the two terminal-block surgeries from a threshold graph, or verify by direct computation that a claimed Type-I or Type-II example fails equality for every admissible k.","tokens_in":16171,"feed_emoji":"📊","tokens_out":1042,"duration_ms":16418,"temperature":0.7,"pith_summary":"The Grone–Merris–Bai theorem bounds the sum of the first k Laplacian eigenvalues of a graph by the sum of the first k terms of its conjugate degree sequence. This paper settles when that bound is tight. Equality holds if and only if the graph is obtained from a threshold graph by one of two local operations at a terminal block: either delete arbitrary edges from the first dominating clique block, or add arbitrary edges inside the first independent block, with k lying in an explicitly described interval controlled by the degrees and components of the modified block. The argument unwinds the proof of the inequality through a split-graph trace inequality, translates every slackness condition into a geometric constraint on an orthogonal projection, and solves those constraints using the known spectrum of threshold graphs. The result gives a complete combinatorial catalogue of all tight pairs (G, k).","feed_headline":"When Laplacian sums hit the degree bound exactly","feed_subtitle":"Equality holds only for two explicit surgeries on threshold graphs, with k pinned by block degrees","key_machinery":"The split-graph trace inequality: for a split graph H with clique K and independent set S and any orthogonal projection Q of rank q with Q1 = 0, tr(Q(L_H − r_0 I)) ≤ e_H(K, S), with equality only when H (or its complement) is threshold and Q has one of two explicit forms built from the eigenspaces of that threshold graph. Unwinding the Grone–Merris chain reduces equality to five simultaneous conditions on a single r_0 and its projection Q_r0; the trace equality forces the threshold structure and pins Q.","core_discovery":"For a graph G and 1 ≤ k ≤ n−1, the equality ∑_{i=1}^k λ_i(G) = ∑_{i=1}^k d_i^*(G) holds if and only if (G, k) belongs to one of two families. Type I graphs arise by replacing the initial dominating clique block of a threshold graph with an arbitrary graph F and taking k between the size of the remaining clique blocks and that size plus min{δ(F), c(F̄)−1}. Type II graphs arise by adding an arbitrary graph F inside the initial independent block of a threshold graph (equivalently, of the complement) and taking k between r_0 + max{Δ(F), |B_1|−c(F)} and r_0 + |B_1|−1.","pith_inferences":["The two families suggest that Grone–Merris tightness is a local deformation of the nested-neighbourhood property that characterises threshold graphs.","The same projection-slackness method should produce equality catalogues for other majorisation inequalities that pass through a split-graph intermediate step.","Once both catalogues are known, one can decide algorithmically, given G and k, whether the bound is tight by checking block structure and a single degree/component condition."],"forward_implications":["Every pair (G, k) that saturates the Grone–Merris bound is completely classified by two explicit combinatorial constructions.","The only graphs that can achieve equality for some k are those obtained from threshold graphs by modifying a single terminal block.","The admissible range of k is completely determined by the minimum/maximum degree and the number of components of the modified block.","The same spectral platform used for Brouwer equality now yields the full Grone–Merris equality catalogue via the split-graph trace inequality."],"fun_headline_variants":["Grone-Merris equality: two surgeries on threshold graphs","Laplacian sums meet degree bound only for two graph families","Equality in Grone-Merris-Bai holds for two explicit families","Tight Grone-Merris pairs come from threshold block surgeries","When Grone-Merris is tight: two threshold-graph operations"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The catalogue of equality cases for the split-graph trace inequality, and the earlier catalogue of equality cases for Brouwer’s conjecture, must both be complete; if either list misses a graph, the reduction that forces G to be one of the two families fails.","fun_headline_variants_meta":{"raw":{"variants":["Grone-Merris equality: two surgeries on threshold graphs","Laplacian sums meet degree bound only for two graph families","Equality in Grone-Merris-Bai holds for two explicit families","Tight Grone-Merris pairs come from threshold block surgeries","When Grone-Merris is tight: two threshold-graph operations"]},"model":"grok-4.5","effort":"low","cost_usd":0.004394,"raw_usage":{"total_tokens":1384,"prompt_tokens":923,"num_sources_used":0,"completion_tokens":75,"cost_in_usd_ticks":43944000,"prompt_tokens_details":{"text_tokens":923,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":386,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":923,"tokens_out":75,"duration_ms":6461,"temperature":1.0,"reasoning_tokens":386,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-30T18:14:35.752577+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a concrete graph G and integer k that attain equality in the Grone–Merris sum but are not obtainable by either of the two terminal-block surgeries from a threshold graph, or verify by direct computation that a claimed Type-I or Type-II example fails equality for every admissible k.","supporting_citations":[],"review_version":1}