Pith. sign in

REVIEW 4 minor 23 references

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

T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read The sum of the k largest Laplacian eigenvalues of a graph is at most the edge count plus k times the matching number, and also at most a simple function of the vertex-cover number, both improving a classical bound in wide ranges of k.

desk verdict Clean proofs of Lew’s two refinements of Brouwer; short, correct, and ready for the literature. read the letter →

arxiv 2607.08452 v2 pith:RZXY7C56 submitted 2026-07-09 math.CO

Junying Lu , Jiabao Yang This is my paper · ORCID
classification math.CO MSC 05C50
keywords Laplacianeigenvaluesumsmatchingnumbervertex-coverpartialspectralgraphtheoryspectramatrix
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

This paper proves two upper bounds on the sum of the k largest Laplacian eigenvalues of a simple graph. One bound replaces the classical quadratic term with k times the matching number (for k at most two less than the number of non-isolated vertices). The other replaces it with k times the vertex-cover number minus a triangular number (once k is at least the cover size). Both strengthen a recently settled classical inequality for large enough k, and both are shown to be tight on natural families such as stars and complete split graphs. The arguments start from the classical inequality and combine it with Edmonds’ characterization of matchings and a spectral comparison that uses a large clique in the complement. A sympathetic reader cares because the new bounds give concrete, parameter-dependent control that is often much tighter than the universal classical estimate once the matching or cover number is known.

What carries the argument

The already-proved classical inequality that the sum of the k largest Laplacian eigenvalues is at most the edge count plus the triangular number of k+1, used together with Edmonds’ min-max theorem for the matching number via odd-set covers and a Weyl-monotonicity argument that extracts a large clique contribution from the complement.

What would settle it

Take any concrete graph with known matching number u (for instance a disjoint union of triangles plus a matching) and compute its ordered Laplacian spectrum; if for some k with 2 u ≤ k ≤ n-2 the partial sum ever exceeds the edge count plus k u, the matching bound is false.

Watch

Extended reading notes

Core claim

For every simple graph with n non-isolated vertices and every integer k between 1 and n-2, the sum of the k largest Laplacian eigenvalues is at most the number of edges plus k times the matching number. Separately, for every graph of order n whose vertex-cover number is t, the same sum is at most the number of edges plus k t minus the triangular number of t, whenever t ≤ k ≤ n.

Load-bearing premise

When an optimal odd-set cover contains no singleton vertices, the graph must still contain at least two odd sets of size greater than one; otherwise the order would be too small for the assumed range of k, and the edge-count estimate inside those sets would fail.

Editorial extensions

If this is right

  • Whenever the matching number is smaller than roughly k/2, the matching bound is strictly stronger than the classical quadratic bound.
  • Whenever the vertex-cover number t is smaller than k, the cover bound improves the classical estimate by a positive quadratic term in t.
  • Equality is attained by stars for the matching bound and by complete split graphs for the cover bound, so the linear coefficients cannot be lowered in general.
  • Both inequalities supply immediately usable a-priori estimates once a matching or vertex cover of the graph is known.

Reading between the lines

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

  • Analogous strengthenings may exist for other classical parameters such as arboricity, degeneracy or clique cover number.
  • The case division at k = 2 u suggests that the most interesting extremal examples for the matching bound lie near that threshold.
  • The same technique of feeding the classical inequality into a min-max covering formula could be tried for the signless Laplacian or for normalized Laplacian partial sums.
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

0 major / 4 minor

Summary. The paper proves two conjectures of Lew on upper bounds for the sum sk(G) of the k largest Laplacian eigenvalues of a simple graph G. Using the recently established Brouwer inequality (Theorem 1 of Kothari–Tudose), Edmonds’ odd-set-cover characterization of the matching number, Weyl monotonicity, and the Laplacian complement relation, the authors show: (i) if G has n non-isolated vertices and 1≤k≤n-2, then sk(G)≤e(G)+k u(G) (Theorem 4); (ii) if au(G)=t and t≤k≤n, then sk(G)≤e(G)+kt-binom(t,2) (Theorem 5, with a separate verification for k=n). Both bounds are shown to be sharp by the star and the complete split graphs Sn,t respectively. The proofs occupy Sections 3–4 and rest on a short list of standard lemmas collected in Section 2.

Significance. Brouwer’s conjecture was a long-standing open problem in spectral graph theory; its recent resolution immediately yields stronger, parameter-dependent refinements. The matching-number bound improves Brouwer’s estimate whenever k≥2 u(G), while the vertex-cover bound improves it for all k> au(G). Both statements had been left open by Lew, and the present short, self-contained arguments close them cleanly. The work therefore supplies two natural and tight strengthenings of a classical spectral inequality, using only classical tools once Brouwer’s theorem is available. Sharpness examples confirm that the constants cannot be improved in general.

minor comments (4)
  1. Page 1, abstract and introduction: the arXiv identifiers of the concurrent independent proof of Conjecture 2 (Huang–Qin) and of the equality characterization of Brouwer (Cai–Chen–Yang–Zhang) are already listed in the references; a single sentence in the introduction noting the concurrent work would improve historical clarity.
  2. Section 3, Case 2 (r=0): the elementary observation that at least two ai must be positive is correct, but a one-line parenthetical reminder that a single odd set of size 2μ+1 would force n≤2μ+1 would make the contradiction with n≥2μ+2 completely transparent to a non-specialist reader.
  3. Lemma 5: the application of Weyl’s monotonicity is standard, yet a brief citation of the precise form used (e.g., Horn–Johnson or Brouwer–Haemers) would be helpful for readers less familiar with matrix inequalities.
  4. Throughout: the notation εk(G)=sk(G)-e(G) is introduced early and used consistently; it would be useful to restate the definition once at the beginning of Section 3 so that the section can be read independently.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the proofs are direct, non-self-referential deductions from the external Kothari–Tudose theorem (Brouwer) plus classical matching and spectral lemmas.

full rationale

The central claims (Theorems 4 and 5) are obtained by case analysis that invokes only external results: Theorem 1 (Kothari–Tudose confirmation of Brouwer), Edmonds’ odd-set-cover characterization (Theorem 3), Weyl monotonicity, the Brouwer–Haemers complement relation (Lemma 4), and elementary counting bounds on edges and sum-of-squares. No quantity is defined in terms of the target inequalities, no parameters are fitted to data and then re-used as predictions, and no load-bearing uniqueness or ansatz is imported via self-citation. The authors’ own concurrent-work acknowledgement and the sharpness examples (stars, complete split graphs) are independent of the derivation chain. The argument is therefore self-contained against its external benchmarks and exhibits none of the six circularity patterns.

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

The paper is a pure combinatorial deduction. It imports Brouwer's inequality (recently proved), Edmonds' min-max theorem for matching number, the Laplacian complement relation of Brouwer–Haemers, Weyl's eigenvalue monotonicity, and elementary facts about non-negative spectra and traces. No free parameters or new physical entities are introduced.

assumptions (5)
  • domain assumption Brouwer's Laplacian inequality sk(G)≤e(G)+binom(k+1,2) holds for every graph (Kothari–Tudose)
    Invoked as Theorem 1 and used as the main black-box engine in both proofs (Sections 3 and 4).
  • standard math Edmonds' theorem: matching number equals minimum weight of an odd-set cover
    Used to choose the cover C of weight ν(G) that splits the edge set in the proof of Conjecture 2.
  • standard math Laplacian eigenvalues of a graph and its complement satisfy λi(G)=n-λn-i(G) for i=1…n-1
    Lemma 4 (Brouwer–Haemers); central to the translation step in the proof of Conjecture 3.
  • standard math Weyl monotonicity: if A-B is positive semidefinite then λi(A)≥λi(B)
    Applied in Lemma 5 to compare a graph with a clique-plus-isolates subgraph.
  • standard math All Laplacian eigenvalues are non-negative and sum to twice the number of edges
    Used for the trivial bounds εk≤e(G) and sn=2e(G).

how reviews work

0 comments
Cite this review

Pith. "Pith review of Proofs of two conjectures on generalizations of Brouwer's Laplacian conjecture." pith.science (2026). https://pith.science/paper/RZXY7C56

@misc{pith2026260708452,
  author       = {Pith},
  title        = {Pith review of: Proofs of two conjectures on generalizations of Brouwer's Laplacian conjecture},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RZXY7C56}},
  note         = {Machine review of arXiv:2607.08452}
}
abstract

Let $G=(V,E)$ be a simple graph of order $n$ and let $\lambda_1(G)\ge \cdots \ge \lambda_n(G)$ be the eigenvalues of its Laplacian matrix. Brouwer conjectured that for every $1\le k\le n$, $\sum_{i=1}^k\lambda_i(G)\le |E|+\binom{k+1}{2}$, which was recently confirmed by Kothari and Tudose. Before Brouwer's conjecture was proved, Lew (JCT-B, 2026) established a weaker form of Brouwer's Laplacian eigenvalue inequality and proposed two conjectures for upper bounds on the sum of the $k$ largest Laplacian eigenvalues, one in terms of the matching number and the other in terms of the vertex-cover number. Using Brouwer's Laplacian inequality, we prove both conjectures.

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

23 extracted references · 4 linked inside Pith

  1. [1]

    Bai, The Grone–Merris conjecture,Trans

    H. Bai, The Grone–Merris conjecture,Trans. Amer. Math. Soc.363(2011), 4463–4474

    2011

  2. [2]

    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

    2012

  3. [3]

    Brouwer, W.H

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

    2012

  4. [4]

    D. Cai, Z. Chen, J. Yang, X.-D. Zhang, On full Brouwer’s Laplacian conjec- ture, arXiv:2607.03388, 2026

    arXiv 2026

  5. [5]

    Chen, Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph,Linear Algebra Appl.557(2018), 327–338

    X. Chen, Improved results on Brouwer’s conjecture for sum of the Laplacian eigenvalues of a graph,Linear Algebra Appl.557(2018), 327–338

    2018

  6. [6]

    Chen, On Brouwer’s conjecture for the sum ofklargest Laplacian eigen- values of graphs,Linear Algebra Appl.578(2019), 402–410

    X. Chen, On Brouwer’s conjecture for the sum ofklargest Laplacian eigen- values of graphs,Linear Algebra Appl.578(2019), 402–410

    2019

  7. [7]

    Cooper, Constraints on Brouwer’s Laplacian spectrum conjecture,Lin- ear Algebra Appl.615(2021), 11–27

    J.N. Cooper, Constraints on Brouwer’s Laplacian spectrum conjecture,Lin- ear Algebra Appl.615(2021), 11–27

    2021

  8. [8]

    Das, S.A

    K.Ch. Das, S.A. Mojallal, I. Gutman, On Laplacian energy in terms of graph invariants,Appl. Math. Comput.268(2015), 83–92

    2015

Show all 23 references
  1. [9]

    Z. Du, B. Zhou, Upper bounds for the sum of Laplacian eigenvalues of graphs, Linear Algebra Appl.436(2012), 3672–3683

    2012

  2. [10]

    Edmonds, Paths, trees, and flowers,Canad

    J. Edmonds, Paths, trees, and flowers,Canad. J. Math.17(1965), 449–467

    1965

  3. [11]

    Ganie, S

    H.A. Ganie, S. Pirzada, B.A. Rather, V. Trevisan, Further developments on Brouwer’s conjecture for the sum of Laplacian eigenvalues of graphs,Linear Algebra Appl.588(2020), 1–18

    2020

  4. [12]

    Grone, R

    R. Grone, R. Merris, The Laplacian spectrum of a graph II,SIAM J. Discrete Math.7(1994), 221–229

    1994

  5. [13]

    Haemers, A

    W.H. Haemers, A. Mohammadian, B. Tayfeh-Rezaie, On the sum of Lapla- cian eigenvalues of graphs,Linear Algebra Appl.432(2010), 2214–2221

    2010

  6. [14]

    Huang, C

    J. Huang, C. Qin, A matching-number refinement of Brouwer’s Laplacian eigenvalue inequality, arXiv:2607.07118, 2026. 10

    2026 arXiv

  7. [15]

    Kothari, S

    P.K. Kothari, S. Tudose, On Brouwer’s Laplacian conjecture, arXiv:2606.12197, 2026

    2026 arXiv

  8. [16]

    Lew, Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs,J

    A. Lew, Partition density, star arboricity, and sums of Laplacian eigenvalues of graphs,J. Combin. Theory Ser. B179(2026), 71–89

    2026

  9. [17]

    Lew, Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209, 2025

    A. Lew, Sums of Laplacian eigenvalues and sums of degrees, arXiv:2508.04209, 2025

    2025 arXiv

  10. [18]

    Lew, An approximate version of Brouwer’s Laplacian conjecture, arXiv:2601.17575, 2026

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

    2026

  11. [19]

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

    2022

  12. [20]

    Z. Lin, K. Wang, The preservation property of Brouwer’s conjecture,Discrete Math. Lett.15(2025), 39–45

    2025

  13. [21]

    Mayank, On variants of the Grone–Merris conjecture,Master’s thesis, Eind- hoven University of Technology, 2010

    2010

  14. [22]

    Torres, V

    G.S. Torres, V. Trevisan, The critical index of Brouwer’s conjecture,Euro- pean J. Combin.132(2026), 104287

    2026

  15. [23]

    K. Wang, Z. Lin, S. Zhang, C. Ye, A proof of Brouwer’s conjecture fork= 3, Linear Algebra Appl.736(2026), 189–213. 11

    2026

Pith tools

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