Pith. sign in

REVIEW 3 major objections 8 minor 1 cited by

A Matching-Number Refinement of Brouwer's Laplacian Eigenvalue Inequality

T0 review · 3 major / 8 minor · reviewed 2026-07-09 · glm-5.2

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Matching number alone bounds Laplacian eigenvalue excess

desk verdict Resolves Lew's conjecture (ε_k ≤ kν for 1 ≤ k ≤ n−2) with full equality characterization. The proof is modular and the core arguments check out. read the letter →

arxiv 2607.07118 v1 pith:L6TMRWC4 submitted 2026-07-08 math.CO

Jing Huang , Chunyan Qin This is my paper · ORCID
classification math.CO MSC 05C5005C7015A18
keywords LaplacianeigenvaluesmatchingnumberBrouwer'sconjectureoddsetcoverspectralgraphtheoryequalitycasesTutte-Bergeformula
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

For a graph G, the quantity ε_k(G) measures how much the sum of the k largest Laplacian eigenvalues exceeds the edge count. Brouwer's conjecture (recently proved) gives a universal bound ε_k(G) ≤ (k+1 choose 2). Lew sharpened this to ε_k(G) ≤ kν(G) + ⌊k/2⌋, where ν(G) is the matching number, and conjectured that the additive ⌊k/2⌋ term is unnecessary in the range 1 ≤ k ≤ n(G)−2. This paper proves that conjecture: ε_k(G) ≤ kν(G) with no correction term, and gives a complete classification of when equality occurs. The argument decomposes the graph using Edmonds' odd set cover theorem into a vertex-cover part (controlled by the vertex-cover bound) and odd-set parts (controlled by the complement identity for Laplacian spectra). This reduces everything to one terminal case — a single dense odd set of size k+1 — which is handled by a local spectral absorption argument showing that a dense packet's spectral gap can strictly absorb an external star forced by the cover's minimality.

What carries the argument

Edmonds' odd set cover theorem decomposes the graph into vertex-cover and odd-set components. The Laplacian complement identity (Lemma 2.10) relates eigenvalue sums of a graph and its complement on the same vertex set. A local absorption argument (Lemmas 4.1–4.3, Theorem 4.4) handles the terminal dense-packet case by showing that the spectral gap of a dense odd set strictly absorbs an external star's contribution, via a tilted star bound that charges the projection's invisible component.

What would settle it

Construct a graph with a minimum-weight odd set cover having exactly one odd set S of size 2q+1 with e(G[S]) > 2q², where every external star's contribution resists absorption — meaning the bound tr(PL(T)) − e(T) ≤ (2q+1)tr(PΠ_W) fails for some star configuration not covered by the four cases in Lemma 4.2.

Watch

Extended reading notes

Core claim

The matching number ν(G) alone, with no additive correction, suffices to bound the Laplacian eigenvalue excess: ε_k(G) ≤ kν(G) for all 1 ≤ k ≤ n(G)−2. Equality holds (up to isolated vertices) only for three families — stars K_{1,n−1}, the join graphs K_1 ∨ (K_k ∪ K_{n−k−1}) with k odd, and nearly-complete graphs K_n − E(K_{1,t}) with n odd and k = n−2. The endpoint range k ≥ n(G)−1, where ε_k(G) = |E|, is classified separately: the inequality fails precisely at k = n−1 for graphs K_{2r+1} − F with |F| < r.

Load-bearing premise

The terminal absorption argument — the most structurally delicate step — requires that when a minimum-weight odd set cover has a single dense odd set S of size 2q+1 with more than 2q² internal edges, at least one external star forced by the cover's singleton vertices can be strictly absorbed into the dense packet's spectral gap. This rests on a case-by-case eigenvalue analysis of a modified Laplacian operator across all configurations of the star's center and leaves relative.

Editorial extensions

If this is right

  • The equality classification provides a complete extremal catalogue for matching-number bounds on Laplacian eigenvalue sums, which can serve as a reference for future spectral-graph inequalities.
  • The endpoint analysis pins down exactly when ε_k(G) ≤ kν(G) fails (k = n−1, nearly-complete odd graphs with too few deleted edges), closing the remaining range left open by the conjecture.
  • The decomposition strategy — odd set cover for structural decomposition, complement identity for spectral transfer, local absorption for terminal cases — is a reusable template for other inequalities linking matching parameters to spectral sums.
  • Since Brouwer's universal bound (k+1 choose 2) is now a theorem and this paper sharpens it to kν(G) ≤ k·(n/2), the gap between the universal and matching-refined bounds is quantified: the matching number captures roughly half of the worst-case bound.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The three equality families suggest a structural trichotomy — sparse (stars), mixed-density (clique joined to independent set), and nearly-complete (complete minus a star) — that may reflect three distinct regimes of how matching constraints interact with spectral concentration.
  • The absorption mechanism could generalize to other settings where a dense substructure's spectral gap must compensate for external contributions, potentially applying to normalized Laplacians or signless Laplacians with analogous matching-number bounds.
  • The fact that the additive ⌊k/2⌋ term vanishes entirely in the non-endpoint range but the endpoint range requires separate treatment suggests a phase transition in how matching number controls spectral sums as k approaches the graph's order.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 8 minor

Summary. This paper proves Conjecture 1.1 of Lew [15], which refines Brouwer's Laplacian eigenvalue inequality to a matching-number bound: for every finite simple graph G with n non-isolated vertices and matching number ν, one has ε_k(G) ≤ kν for all 1 ≤ k ≤ n−2, where ε_k(G) is the excess of the sum of the k largest Laplacian eigenvalues over the edge count. The paper also provides a complete characterization of equality cases (Theorem 1.2) and a separate analysis of the endpoint range k ≥ n−1 (Theorem 1.3), identifying exactly when the inequality fails or holds with equality. The proof strategy combines Edmonds' odd set cover theorem, Lew's vertex-cover and k/2 bounds, the Laplacian complement identity, and a novel terminal absorption argument for the dense single-packet case.

Significance. The result resolves a natural conjecture that improves the known bound ε_k(G) ≤ kν(G) + ⌊k/2⌋ by removing the additive term in the non-endpoint range. The equality characterization is a valuable addition, giving a sharp structural result. The proof is modular and builds on established tools (odd set covers, Ky Fan's principle, complement identity) while introducing a nontrivial local absorption mechanism (Section 4) to handle the terminal case. The endpoint analysis (Theorem 1.3) via the Erdős–Gallai theorem is a clean complement. The paper is a solid contribution to the spectral graph theory program surrounding Brouwer-type inequalities.

major comments (3)
  1. [Lemma 4.2, Case 3 (b > 0, 0 < a < m)] This is the most computation-heavy step in the paper. The characteristic polynomial is factored as (t+m)g(t) with g(t) given in Eq. (6). The argument that g has at most two positive roots proceeds by contradiction using Vieta's formulas: the sum of roots a+b−2m+2 > 0 forces b > 2m−2−a ≥ m−1, while the product −(m−a)(b−m+1) > 0 (with m−a > 0) forces b < m−1, yielding the contradiction. This logic is correct. However, the subsequent bound on the sum of the two positive roots θ₁+θ₂ ≤ a+b−m+2 ≤ b+1 uses θ₃ ≥ −m, which is justified by the observation z^T M_T z ≥ −m‖z‖². This observation should be stated more explicitly: it follows because z^T L(T)z ≥ 0 (L(T) is positive semidefinite) and z^T(−mΠ_W)z = −m‖Π_W z‖² ≥ −m‖z‖². As written, the inequality z^T M_T z ≥ −m‖z‖² is asserted without this one-line justification. This is a presentation gap, not a correctness issue, but given that the entire
  2. [Lemma 4.3, numerical estimate (11)] The estimate (11) states ∆ − β + min{2q, (2q+1)α} < 2q. When β ≤ ∆, the substitution α ≤ β/(q+∆) gives ∆ − β + (2q+1)β/(q+∆) ≤ ∆(2q+1)/(q+∆). The final step uses ∆(2q+1)/(q+∆) < 2q, which requires ∆ < 2q². Since ∆ ≤ q and q ≥ 1, we have ∆(2q+1) ≤ q(2q+1) = 2q² + q, and (q+∆) ≥ q+1, so the ratio is at most (2q²+q)/(q+1) = 2q − q/(q+1) < 2q. The bound is correct but the intermediate algebra is compressed into a single line. Expanding this to two lines would aid verification.
  3. [Theorem 1.2, equality characterization, case k = 2q] In the equality analysis for k = 2q (i.e., k = |S|−1), the argument rules out equality by showing that the unique maximizing subspace U for H = K_S (the positive eigenspace of L(K_S) restricted to S) cannot contain z_T for any external star T, because z_T has a nonzero coordinate outside S. This is correct. However, the argument first establishes that e(H) = kq forces H to be connected (otherwise e(H) ≤ C(2q,2) < 2q² = kq), and then that L(H) has exactly k positive eigenvalues with positive eigenspace U. The connectivity claim uses e(H) = 2q² and the fact that a disconnected graph on 2q+1 vertices has at most C(2q,2) = q(2q−1) = 2q² − q < 2q² edges. This is fine, but the paper should state this bound explicitly rather than leaving it as 'otherwise e(H) ≤ C(2q,2) < 2q² = kq.'
minor comments (8)
  1. [Abstract] The abstract uses K_{n-k-1} with a bar (overline) in one place and without in another. In the abstract it reads 'K_1 ∨ (K_k ∪ overline{K_{n-k-1}})' while in Theorem 1.2(ii) it reads 'F_{k,n-k-1} = K_1 ∨ (K_k ∪ K_{n-k-1})'. The overline in the abstract likely denotes the empty graph (complement of K_{n-k-1}), which is the same as K_{n-k-1} in the theorem statement if the latter denotes the empty graph. This notation should be unified.
  2. [Section 2, Lemma 2.10] The complement identity is stated with G and its complement Ḡ, but the bar notation for complement is not introduced before use. A brief note that Ḡ denotes the complement of G would help.
  3. [Section 4, Lemma 4.1] The statement 'every component of H̄ has at most q−∆+1 vertices' is used to apply Lemma 2.7. The connection is that H̄ has q−∆ edges on 2q+1 vertices, so its largest component has at most q−∆+1 vertices (since a component with more vertices would have more edges). This is correct but the reasoning is implicit.
  4. [Section 5, Proof of Theorem 1.2] In the converse verification for G = F_{k,n-k-1} with k odd, the spectrum is listed as {n, (k+1)^{[k-1]}, 1^{[s]}, 0} where s = n−k−1. The computation ε_k(G) = n + (k−1)(k+1) − (n−1) − C(k,2) should simplify to k(k+1)/2 = kν. An intermediate step showing this simplification would be helpful.
  5. [Remark 5.9] The remark notes that F_{k,1} ≅ D_{k+2,k} for odd k. It would be useful to also note that D_{n,t} with t = n−2 (the maximum allowed) gives K_n minus a star K_{1,n-2}, which is K_{1,n-1} plus an edge, connecting to the star family.
  6. [References] References [13], [14], [15] are dated 2026, which appears to be a future date. If these are preprints, the arXiv identifiers should be checked for consistency.
  7. [Section 3, Lemma 3.1] The proof handles k = 0 separately, but the statement says 0 ≤ k ≤ 2q+1. The case k = 0 gives ε_0(H) = −e(H) ≤ 0, which is consistent with kq = 0. This is fine but could be noted more explicitly.
  8. [Section 5, Proof of Theorem 1.3] The proof uses Lemma 2.11 for the case n ≥ 2ν+2. Lemma 2.11 is stated for N-vertex graphs with no isolated vertices and matching number ν ≥ 1, writing N = 2ν + s with s ≥ 2. The application is correct but the reader needs to match the notation (N in Lemma 2.11 vs. n in Theorem 1.3).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found; derivation is self-contained with independent external citations

full rationale

The paper proves Conjecture 1.1 (Lew's conjecture) that ε_k(G) ≤ kν(G) for 1 ≤ k ≤ n(G)−2. The derivation chain is self-contained and does not reduce to its inputs by construction. The key tools are: (1) Edmonds' odd set cover theorem (Lemma 2.4, cited from [18, Lovász–Plummer]) — an external, well-established result expressing ν(G) as the minimum weight of an odd set cover; (2) Lew's vertex-cover bound ε_k(G) ≤ kτ(G) (Lemma 2.2, cited from [15]) — used as a strict input, not circularly, since the paper strengthens Lew's own bound ε_k ≤ kν + ⌊k/2⌋ by removing the additive term; (3) Lew's ε_k ≤ k/2 bound (Lemma 2.9, cited from [16]) — again used as an input to derive a stronger result; (4) the Laplacian complement identity (Lemma 2.10) — a standard algebraic identity proved in-line. The terminal absorption argument (Lemmas 4.1–4.3, Theorem 4.4) is entirely self-contained: it combines a spectral gap estimate (Lemma 4.1, proved via the complement identity and Lemma 2.7) with a projection trace bound (Lemma 4.2, proved by explicit case analysis of characteristic polynomials) to show strict inequality for dense packets. The Brouwer conjecture resolution by Kothari–Tudose [13] is cited only in Lemma 5.1 for context on equality cases, not as a load-bearing input to the main inequality. No step reduces to its inputs by definition, no prediction is fitted to data, and no self-citation chain forces the conclusion. The cited results (Edmonds, Tutte–Berge, Erdős–Gallai, Ky Fan) are all external, parameter-free mathematical theorems with independent verification.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The paper is a pure mathematics proof with no free parameters, no invented entities, and no ad hoc assumptions. All axioms are standard results from matching theory and spectral graph theory, cited from the prior literature. The proof is parameter-free.

assumptions (7)
  • standard math Edmonds' odd set cover theorem: ν(G) = w(C) for a minimum-weight odd set cover C
    Invoked in Lemma 2.4, cited from [18]. Standard result in matching theory, used to decompose G into G_vc and G_odd.
  • standard math Tutte–Berge formula for matching number
    Invoked in Lemma 2.6, cited from [18]. Used in Lemma 2.11 for the endpoint extremal edge-count bound.
  • standard math Erdős–Gallai extremal matching theorem
    Invoked in Lemma 2.5, cited from [7]. Used in Theorem 1.3 for endpoint classification.
  • standard math Ky Fan maximum principle for eigenvalue sums
    Invoked in Lemma 2.8, cited from [8]. Variational characterization of sum of k largest eigenvalues, used throughout §4.
  • standard math Lew's bound ε_k(G) ≤ k/2 (Lemma 2.9)
    Cited from [16]. Used in Lemma 3.1 to bound odd-set contributions. This is a published result by a different author.
  • standard math Lew's vertex-cover bound ε_k(G) ≤ kτ(G) (Lemma 2.2)
    Cited from [15]. Used in Theorem 3.4 to bound the singleton-covered edge contribution. Published result by a different author.
  • standard math Laplacian complement identity (Lemma 2.10)
    Standard spectral graph theory identity relating ε_k(G) to ε_{|V|-k-1}(Ḡ). Used in Lemma 3.1 and Lemma 5.3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Matching-Number Refinement of Brouwer's Laplacian Eigenvalue Inequality." pith.science (2026). https://pith.science/paper/L6TMRWC4

@misc{pith2026260707118,
  author       = {Pith},
  title        = {Pith review of: A Matching-Number Refinement of Brouwer's Laplacian Eigenvalue Inequality},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/L6TMRWC4}},
  note         = {Machine review of arXiv:2607.07118}
}
abstract

Let $G=(V,E)$ be a finite simple graph with Laplacian eigenvalues $\lambda_1(L(G))\ge\cdots\ge\lambda_{|V|}(L(G))$, and define \[ \eps_k(G)= \sum_{j=1}^{\min\{k,|V|\}}\lambda_j(L(G))-|E|. \] Let $\nu(G)$ be the matching number of $G$, and let $n(G)$ be the number of non-isolated vertices of $G$. Lew proved that \(\eps_k(G)\le k\nu(G)+\lfloor k/2\rfloor\), and conjectured that the additive term can be removed in the non-endpoint range. We prove this conjecture: \[ \eps_k(G)\le k\nu(G) \qquad (1\le k\le n(G)-2). \] We also characterize all equality cases. Up to isolated vertices, equality holds precisely for stars, for \(K_1\vee(K_k\cup\overline{K_{n-k-1}})\) with \(k\) odd, and for \(K_n-E(K_{1,t})\) with \(n\) odd, \(k=n-2\), and \(1\le t\le n-2\). We also analyze the endpoint range \(k\ge n(G)-1\), where \(\eps_k(G)=|E|\), and determine the specific cases where the inequality \(\varepsilon_k(G)\le k\nu(G)\) fails or holds with equality.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Proofs of two conjectures on generalizations of Brouwer's Laplacian conjecture

    math.CO 2026-07 accept novelty 6.0 of 10

    Using the settled Brouwer Laplacian theorem, both of Lew's conjectures bounding the sum of the k largest Laplacian eigenvalues by matching number and by vertex-cover number are proved.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages · cited by 1 Pith paper

  1. [13]

    P. K. Kothari and S. Tudose, On Brouwer’s Laplacian conjecture, arXiv:2606.12197 [math.CO], 2026. 19

    work page Pith review arXiv 2026

  2. [15]

    Lew, Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs, Journal of Combinatorial Theory, Series B, 179 (2026) 71–89

    A. Lew, Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs, Journal of Combinatorial Theory, Series B, 179 (2026) 71–89

    work page 2026

  3. [1]

    Berndsen, Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

    J. Berndsen, Three problems in algebraic combinatorics, Master’s thesis, Eindhoven University of Technology, 2012

    work page 2012

  4. [2]

    A. E. Brouwer and W. H. Haemers.Spectra of Graphs, Universitext, Springer, New York, 2012

    work page 2012

  5. [3]

    More on the full Brouwer Laplacian spectrum conjecture

    X. Chen and J. Zi, More on the full Brouwer’s Laplacian spectrum conjecture, arXiv:2503.11165 [math.CO], 2025

    work page Pith review arXiv 2025

  6. [4]

    J. N. Cooper, Constraints on Brouwer’s Laplacian spectrum conjecture,Linear Algebra and its Applications, 615 (2021) 11–27

    work page 2021

  7. [5]

    K. C. Das, S. A. Mojallal, and I. Gutman, On Laplacian energy in terms of graph invariants, Applied Mathematics and Computation, 268 (2015) 83–92

    work page 2015

  8. [6]

    Edmonds, Paths, trees, and flowers,Canadian Journal of Mathematics, 17 (1965) 449–467

    J. Edmonds, Paths, trees, and flowers,Canadian Journal of Mathematics, 17 (1965) 449–467

    work page 1965

Show all 22 references
  1. [7]

    Erdős and T

    P. Erdős and T. Gallai, On maximal paths and circuits of graphs,Acta Mathematica Academiae Scientiarum Hungaricae, 10 (1959) 337–356

    1959

  2. [8]

    Fan, On a theorem of Weyl concerning eigenvalues of linear transformations:I,Proceedings of the National Academy of Sciences of the United States of America, 35 (1949) 652–655

    K. Fan, On a theorem of Weyl concerning eigenvalues of linear transformations:I,Proceedings of the National Academy of Sciences of the United States of America, 35 (1949) 652–655

    1949

  3. [9]

    Fritscher, C

    E. Fritscher, C. Hoppen, I. Rocha, and V. Trevisan, On the sum of the Laplacian eigenvalues of a tree,Linear Algebra and its Applications, 435(2) (2011) 371–399

    2011

  4. [10]

    H. A. Ganie, S. Pirzada, B. A. Rather, and V. Trevisan, Further developments on Brouwer’s conjectureforthesumofLaplacianeigenvaluesofgraphs,Linear Algebra and its Applications, 588 (2020) 1–18

    2020

  5. [11]

    H. A. Ganie, S. Pirzada, and V. Trevisan, On the sum ofk largest Laplacian eigenvalues of a graph and clique number,Mediterranean Journal of Mathematics, 18 (2021) 15

    2021

  6. [12]

    W. H. Haemers, A. Mohammadian, and B. Tayfeh-Rezaie, On the sum of Laplacian eigenvalues of graphs,Linear Algebra and its Applications, 432 (2010) 2214–2221

    2010

  7. [14]

    Lew, An approximate version of Brouwer’s Laplacian conjecture, arXiv:2601.17575 [math.CO], 2026

    A. Lew, An approximate version of Brouwer’s Laplacian conjecture, arXiv:2601.17575 [math.CO], 2026

    2026

  8. [16]

    Lew, Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209 [math.CO], 2025

    A. Lew, Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209 [math.CO], 2025

    2025 arXiv

  9. [17]

    W. J. Li and J. M. Guo, On the full Brouwer’s Laplacian spectrum conjecture,Discrete Mathematics, 345(12) (2022) 113078

    2022

  10. [18]

    Lovasz and M

    L. Lovasz and M. D. Plummer.Matching Theory, AMS Chelsea Publishing, 2009

    2009

  11. [19]

    M. L. Overton and R. S. Womersley, Optimality conditions and duality theory for minimizing sums of the largest eigenvalues of symmetric matrices,Mathematical Programming, 62 (1993) 321–357

    1993

  12. [20]

    Rocha, Brouwer’s conjecture holds asymptotically almost surely,Linear Algebra and its Applications, 597 (2020) 198–205

    I. Rocha, Brouwer’s conjecture holds asymptotically almost surely,Linear Algebra and its Applications, 597 (2020) 198–205

    2020

  13. [21]

    G. S. Torres and V. Trevisan, Brouwer’s conjecture for the Cartesian product of graphs, Linear Algebra and its Applications, 685 (2024) 66–76

    2024

  14. [22]

    G. S. Torres and V. Trevisan, The critical index of Brouwer’s conjecture,European Journal of Combinatorics, 132 (2026) 104287. 20

    2026

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.