{"id":"b884def6-b799-42b4-80fa-54abd0fbc44c","arxiv_id":"2607.07118","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":0,"one_line_summary":"The inequality ε_k(G) ≤ kν(G) holds for all graphs in the range 1≤k≤n(G)−2, resolving Lew's conjecture, with all equality cases characterized.","lead":"The paper proves a conjecture by Lew that sharpens Brouwer's Laplacian eigenvalue inequality: for any graph with matching number ν and n non-isolated vertices, the excess ε_k(G) of the sum of the k largest Laplacian eigenvalues over the edge count is at most kν for 1≤k≤n−2. It also fully classifies the equality cases and analyzes the endpoint range k≥n−1.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"No significant objection identified. Lemma 4.2 Case 3 verified step-by-step; the Vieta argument and numerical estimate in Lemma 4.3 are correct.","rationale":"The reader correctly identified the load-bearing step (Lemma 4.2 Case 3 and the terminal absorption argument). Having carefully verified the Vieta's formula argument, the eigenvalue lower bound θ₃ ≥ -m, the numerical estimate in Lemma 4.3, and the equality characterization logic, I find no error. The proof is modular, self-contained given standard tools (Edmonds' theorem, Ky Fan's principle, Brouwer's conjecture via [13]), and the equality cases are verified by direct spectral computation. The concern about formal verification of the matrix computations is reasonable as a suggestion for future work, but the hand-verification succeeds. Verdict remains ACCEPT.","tokens_in":19843,"tokens_out":5577,"duration_ms":206090,"concrete_test":"Independently verify the characteristic polynomial of the 4×4 matrix in Lemma 4.2 Case 3 (b > 0, 0 < a < m) by direct expansion, confirming it equals (t+m)·g(t) with g(t) as in (6). Then numerically test the eigenvalue sum bound for specific values, e.g., q=2 (m=5), a=2, b=3: compute eigenvalues of M_T and verify the sum of the largest 4 positive eigenvalues is ≤ 5 = d.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader correctly identifies Lemma 4.2 (specifically Case 3 with b > 0 and 0 < a < m) as the most computation-heavy step. Having traced through it: the characteristic polynomial (t+m)g(t) with g(t) given by (6) is analyzed via Vieta's formulas. The contradiction argument showing g has at most two positive roots is valid: 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, giving the desired contradiction. The bound θ₁+θ₂ ≤ a+b-m+2 ≤ b+1 (using θ₃ ≥ -m, which follows from z^T M_T z ≥ -m||z||²) is correct. The total positive eigenvalue sum ≤ (a-1)+(b+1) = d follows. In Lemma 4.3, the numerical estimate (11): when β ≤ ∆, substituting α ≤ β/(q+∆) gives ∆-β+(2q+1)β/(q+∆) ≤ ∆(2q+1)/(q+∆) < 2q since ∆ < 2q² (as ∆ ≤ q). All steps check out. The equality characterization in Theorem 1.2 is also tight: the strict inequalities from Lemma 3.3 (c ≥ 2) and Lemma 5.8 (star + external star) correctly eliminate all non-listed cases. No internal inconsistency or hidden assumption found.","agreement_with_reader":"agree"},"referee_report":{"model":"glm-5.2","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.","tokens_in":20126,"tokens_out":2171,"duration_ms":324629,"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":[{"comment":"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","section":"Lemma 4.2, Case 3 (b > 0, 0 < a < m)"},{"comment":"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.","section":"Lemma 4.3, numerical estimate (11)"},{"comment":"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.'","section":"Theorem 1.2, equality characterization, case k = 2q"}],"minor_comments":[{"comment":"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.","section":"Abstract"},{"comment":"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.","section":"Section 2, Lemma 2.10"},{"comment":"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.","section":"Section 4, Lemma 4.1"},{"comment":"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.","section":"Section 5, Proof of Theorem 1.2"},{"comment":"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.","section":"Remark 5.9"},{"comment":"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.","section":"References"},{"comment":"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.","section":"Section 3, Lemma 3.1"},{"comment":"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).","section":"Section 5, Proof of Theorem 1.3"}],"recommendation":"minor_revision","confidential_remarks":"The paper is mathematically sound. The main theorem resolves a stated conjecture, and the proof has been verified step-by-step including the delicate Case 3 of Lemma 4.2 and the numerical estimate in Lemma 4.3. The major comments are all presentation-level: the algebra in the most computation-heavy steps is correct but compressed, and expanding it would make verification easier for readers. The equality characterization is tight and the endpoint analysis is clean. I recommend minor revision to address the presentation gaps noted above. The 2026 dates on references [13]–[15] should be verified; if these are genuinely future-dated preprints, the journal should confirm availability."},"author_rebuttal":null,"desk_editor":{"model":"glm-5.2","letter":"This paper resolves Lew's Conjecture 1.1: for any finite simple graph G with n non-isolated vertices and matching number ν, ε_k(G) ≤ kν for all 1 ≤ k ≤ n−2. It also gives a complete equality characterization and a separate endpoint analysis for k ≥ n−1. The result is a clean sharpening of Brouwer's Laplacian eigenvalue inequality, replacing the universal (k+1 choose 2) bound with a matching-number-dependent one and removing Lew's additive floor(k/2) term. This is a solid contribution to spectral-combinatorial graph inequalities, not a field-shaper, but a natural and well-motivated result that closes an explicitly stated open problem. The proof architecture is genuinely well-designed. The key idea is to decompose G via a minimum-weight Edmonds odd set cover into a vertex-cover part (controlled by Lew's τ-bound) and an odd-sets part (controlled by the complement identity plus Lew's k/2 bound). This reduces everything to a single terminal case: one dense odd packet S of size 2q+1 with e(G[S]) > 2q². That case is handled by a local absorption argument (Lemma 4.2–4.3) that uses a variational projection to show a dense packet has enough spectral gap to strictly absorb an external star forced by minimality of the cover. The equality tracking through §5 is careful and the three extremal families are verified by direct spectral computation. The stress-test concern was whether the case analysis in Lemma 4.2, particularly Case 3 (0 < a < m, b > 0) with its cubic polynomial g(t), actually holds. I traced through it. The Vieta contradiction (sum of roots forces b > m−1, product forces b < m−1) is valid. The bound θ₁+θ₂ ≤ b+1 using θ₃ ≥ −m is correct, and the numerical estimate in Lemma 4.3 (inequality (11)) checks out with ∆ ≤ q. No hidden assumptions, no circularity. The inputs from Lew [15,16] and Kothari–Tudose [13] are used as black-box tools, not circularly. The soft spots are minor. The matrix computations in Lemma 4.2 are the kind of thing that would benefit from a formal verification pass or at least an appendix with intermediate steps spelled out more — the jump from the 4×4 matrix to the characteristic polynomial (t+m)g(t) is stated without derivation. The endpoint analysis (Theorem 1.3) is less deep than the main theorem; it is essentially an extremal edge-count problem solved via Erdős–Gallai, which is fine but straightforward. Overall: the paper does what it claims, the proof is sound, and the equality characterization is tight. It deserves a serious referee who can independently verify the Lemma 4.2 computations line by line.","headline":"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.","tokens_in":20678,"tokens_out":710,"would_cite":true,"duration_ms":67894,"reading_group":"no","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C70","15A18"],"pacs":[],"model":"glm-5.2","headline":"Matching number alone bounds Laplacian eigenvalue excess","keywords":["Laplacian eigenvalues","matching number","Brouwer's conjecture","odd set cover","spectral graph theory","equality cases","Tutte-Berge formula"],"falsifier":"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.","tokens_in":19910,"feed_emoji":"📊","tokens_out":2496,"duration_ms":52384,"temperature":0.7,"pith_summary":"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.","feed_headline":"Matching number alone bounds Laplacian eigenvalue excess","feed_subtitle":"Settles a conjecture that the matching number — with no additive correction — controls Laplacian eigenvalue sums, and classifies all extrem","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Matching number alone bounds Laplacian eigenvalue excess","No additive correction needed for Laplacian eigenvalue bound","Laplacian eigenvalue excess bounded solely by matching number","Matching number sharpens Brouwer's eigenvalue inequality","Eigenvalue excess controlled by matching number alone"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Matching number alone bounds Laplacian eigenvalue excess","No additive correction needed for Laplacian eigenvalue bound","Laplacian eigenvalue excess bounded solely by matching number","Matching number sharpens Brouwer's eigenvalue inequality","Eigenvalue excess controlled by matching number alone"]},"model":"glm-5.2","effort":"low","cost_usd":0.0,"raw_usage":{"total_tokens":816,"prompt_tokens":739,"completion_tokens":77,"prompt_tokens_details":null},"tokens_in":739,"tokens_out":77,"duration_ms":27204,"temperature":1.0,"reasoning_tokens":null,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-09T19:46:05.451931+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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.","supporting_citations":[],"review_version":1}