REVIEW 1 major objections 6 minor 7 references
The Equality Cases for the Grone-Merris-Bai Theorem
T0 review · 1 major / 6 minor · reviewed 2026-07-30 · grok-4.5
Pith's one-line read Equality in the Grone–Merris–Bai bound holds exactly for two surgical modifications of threshold graphs.
desk verdict Clean equality-case classification for Grone–Merris; the “exactly one of two families” wording is wrong but the inclusive description looks right and fixable. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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.
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 (1)
- [§6.1, Theorem 6.1] 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
minor comments (6)
- [§6.2, Case A degree platform] 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.
- [§4, Theorem 4.1 Case 2; §6.1, Type II] 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.
- [§3, Proposition 3.1] 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.
- [§5, Proposition 5.2(i)] 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.
- [§2.3, Theorem 2.3] 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.
- [General] 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.
Circularity Check
No definitional circularity; mild load-bearing self-citation of the authors' own Brouwer equality catalogue, used as a black box for a different theorem.
-
self citation load bearing
[Theorem 4.1 proof, inequality (7); also Abstract and §1]
"Inequality (7) is the Brouwer inequality, with equality if and only if H is a threshold graph with clique number r_0, by Theorem 2.3. ... together with the recent characterization of the Brouwer equality cases by Cai, Chen, Yang and Zhang (2027)"
The equality catalogue that forces H to be threshold (and thereby pins the form of Q in Cases 1–2 of Theorem 4.1) is imported from the authors’ own prior paper [3] on Brouwer equality, not from an external source. This step is load-bearing for the necessity direction of Theorem 6.1. It is not definitional circularity: [3] concerns a different inequality and does not presuppose GM equality cases; the present paper still supplies independent spectral and combinatorial analysis. Mild sequential self-citation only.
full rationale
The derivation of Theorem 6.1 is not circular in the definitional or fitted-input sense. Grone–Merris equality is reduced, via the A_r ≤ B_r ≤ C_r chain and Lemma 5.1, to five explicit conditions (Proposition 5.2). Those conditions are then solved by (i) the external Kothari–Tudose split-graph trace inequality, (ii) Bai’s theorem, and (iii) a fresh spectral analysis of terminal-block edits of threshold graphs (Sections 3–4 and 6.2–6.3). The only self-dependence is Theorem 2.3 (Brouwer equality cases from the same author group [3]), invoked inside the proof of Theorem 4.1 to force the split graph H to be threshold when the trace inequality is tight. That is ordinary sequential research on a distinct conjecture; [3] does not assume GM equality cases, and the bulk of the paper (eigenvector catalogues, Rayleigh-quotient constraints on Q, degree/spectral platforms for Types I–II) is independent content. No equation is equal to its input by construction, and no parameter is fitted then re-predicted. Score 2 reflects one load-bearing self-citation that does not collapse the central claim.
Assumptions & free parameters
assumptions (6)
- domain assumption Bai’s theorem: Laplacian eigenvalue sequence is majorized by the conjugate degree sequence (Theorem 1.1 / [1,5]).
- domain assumption Kothari–Tudose split-graph trace inequality and its role in proving Brouwer (Lemma 3.3 of [6], restated as Theorem 4.1).
- domain assumption Brouwer equality holds iff G is a threshold graph with clique number k+1 (Theorem 2.3 / [3]).
- standard math Courant–Fischer / variational characterization of eigenvalue sums; orthogonal projections onto spectral subspaces.
- domain assumption Equivalent characterizations of threshold graphs (creation sequence, nested neighborhoods, forbidden induced P4/C4/2K2) — Mahadev–Peled / Chvátal–Hammer.
- ad hoc to paper Explicit Laplacian spectrum and eigenvectors of threshold graphs (Proposition 3.1).
invented entities (2)
-
Type I family (lower terminal clique-block replacement)
independent evidence
-
Type II family (upper terminal independent-block replacement)
independent evidence
Cite this review
Pith. "Pith review of The Equality Cases for the Grone-Merris-Bai Theorem." pith.science (2026). https://pith.science/paper/DGPXRJCZ
@misc{pith2026260723583,
author = {Pith},
title = {Pith review of: The Equality Cases for the Grone-Merris-Bai Theorem},
year = {2026},
howpublished = {\url{https://pith.science/paper/DGPXRJCZ}},
note = {Machine review of arXiv:2607.23583}
}
abstract
The Grone--Merris inequality, conjectured by Grone and Merris~(1994) and first proved by Bai~(2011), states that for every graph $G$ of order $n$ and every $1\le k\le n$, $\sum_{i=1}^k\lambda_i(G)\le\sum_{i=1}^k d_i^*(G)$, where $\lambda_1\ge\cdots\ge\lambda_n$ are the Laplacian eigenvalues and $d_1^*\ge\cdots\ge d_n^*$ is the conjugate degree sequence. In this paper we determine exactly when equality holds. Using the split-graph trace inequality developed by Kothari and Tudose~(2026) in their proof of Brouwer's Laplacian conjecture---which relies on Bai's theorem and also establishes the equivalence between the two conjectures---together with the recent characterization of the Brouwer equality cases by Cai, Chen, Yang and Zhang~(2027), we prove that equality holds in the Grone--Merris inequality if and only if the graph $G$ belongs to one of two explicitly described families. Both families are obtained from a threshold graph by a surgical operation at one terminal block: in the first family, edges are removed from the initial dominating block; in the second, edges are added inside the initial isolated block. Our analysis yields a complete combinatorial description of all pairs $(G,k)$ for which the Grone--Merris bound is tight.
Reference graph
Works this paper leans on
-
[3]
and Zhang X.-D.,On full Brouwer’s Laplacian conjecture, arXiv:2607.03388 (2026)
Cai D., Chen Z., Yang J. and Zhang X.-D.,On full Brouwer’s Laplacian conjecture, arXiv:2607.03388 (2026). arXiv:2607.03388
arXiv 2026
-
[1]
Bai H.,The Grone–Merris conjecture, Trans. Amer. Math. Soc. 363 (2011), 4463–4474. doi:10.1090/S0002-9947-2011-05393-6
-
[2]
Brouwer A. E. and Haemers W. H.,Spectra of graphs, Universitext, Springer, New York, 2012. doi:10.1007/978-1-4614-1939-6
-
[4]
Chv’atal V. and Hammer P. L.,Aggregation of inequalities in inte- ger programming, Annals of Discrete Mathematics 1 (1977), 145–162. doi:10.1016/S0167-5060(08)70731-3
-
[5]
and Merris R.,The Laplacian spectrum of a graph II, SIAM J
Grone R. and Merris R.,The Laplacian spectrum of a graph II, SIAM J. Discrete Math. 7 (1994), 221–229. doi:10.1137/S0895480191222653
-
[6]
Kothari P. K. and Tudose S.,On Brouwer’s Laplacian conjecture, arXiv:2606.12197 (2026). arXiv:2606.12197
arXiv 2026
-
[7]
Mahadev N. V. R. and Peled U. N.,Threshold graphs and related top- ics, Annals of Discrete Mathematics 56, North-Holland, Amsterdam, 1995. ISBN: 978-0-444-89287-4. 16
1995
Reviewed July 30, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.