{"id":"cd9a05a8-cba8-4e60-af98-33107bfbab9b","arxiv_id":"2607.08452","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Lew's matching-number and vertex-cover conjectures on sums of the largest Laplacian eigenvalues are proved from Brouwer's inequality.","lead":"This paper proves two conjectures of Lew that upper-bound the sum of a graph's largest Laplacian eigenvalues by its matching number or its vertex-cover number. The results strengthen Brouwer's recently settled inequality in natural parameter regimes and close a short line of work in spectral graph theory.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript is a short pure-mathematics note whose only external input is the recently settled Brouwer inequality. Every subsequent step is elementary linear algebra or matching theory and can be checked by hand. The single potential soft spot identified by the reader is in fact airtight: the contradiction n≤2μ+1 versus n≥2μ+2 forces at least two positive a_i, after which the quadratic bound closes the estimate. The vertex-cover half is equally clean. Concurrent independent work on Conjecture 2 is acknowledged. Consequently the reader’s ACCEPT / HIGH / low-risk assessment stands; no adjustment is warranted.","tokens_in":8137,"tokens_out":543,"duration_ms":4999,"concrete_test":"Independently recompute the Laplacian spectrum of the star K_{1,n-1} and of the complete split graph S_{n,t} for several pairs (n,k) and (n,t) with t≤k≤n; verify that equality holds exactly as claimed in Remarks 1–2. If either family fails equality, the sharpness (and therefore the tightness of the case analysis) would be compromised.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 4–5) rest on Brouwer’s inequality (now Theorem 1), Edmonds’ odd-set-cover characterization, Weyl monotonicity, and elementary counting. The reader’s flagged step—when r=0 the cover must have at least two positive a_i, else n≤2μ+1 contradicts n≥2μ+2—is correct: a single odd set of size 2μ+1 would force every non-isolated vertex into that set, violating the order lower bound. The subsequent sum-of-squares bound ∑a_i^{2}≤(μ-1)^{2}+1 then yields e(G_{2})≤2μ^{2}-3μ+4≤kμ under k≥2μ and μ≥2. The complementary case r≥1 and the vertex-cover argument via the complement clique (Lemma 5 + Lemma 4) are likewise free of gaps. Sharpness examples (star, complete split graphs) confirm the constants are tight. No hidden assumption or circularity appears.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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\nu(G) (Theorem 4); (ii) if \tau(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.","tokens_in":8346,"tokens_out":772,"duration_ms":7110,"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\nu(G), while the vertex-cover bound improves it for all k>\tau(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.","major_comments":[],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is short, correct, and of clear interest to the spectral-graph-theory community. The concurrent independent proof of Conjecture 2 by Huang–Qin is properly acknowledged; no priority or citation issues arise. Fit for a short note or research announcement in a combinatorial journal is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This note settles both of Lew’s 2026 conjectures on Laplacian eigenvalue sums—one with matching number, one with vertex-cover number—by feeding the newly proved Brouwer inequality into standard tools. That is the whole contribution, and it is real: the statements were open, the proofs are complete, and the constants are shown to be sharp.\n\nWhat they do well is keep the arguments short and case-clean. For the matching-number bound they split on k versus 2ν, invoke Edmonds’ odd-set cover, partition the edges into those hitting the singleton vertices and those inside the odd sets, then bound each piece separately (Lemma 2 plus elementary counting). The delicate r=0 subcase is handled correctly: a single positive a_i would force n ≤ 2μ+1, contradicting n ≥ 2μ+2, so the sum-of-squares estimate closes. For the vertex-cover bound they pass to the complement (where the independent set becomes a clique), apply a simple clique-sum lemma derived from Brouwer plus Weyl, and unwind the complement eigenvalue relation. Both sharpness examples (stars and complete split graphs) work. Concurrent independent work on the matching case is acknowledged.\n\nSoft spots are minor. The paper is entirely derivative of Kothari–Tudose; once Brouwer is available the rest is careful bookkeeping rather than a new idea. The r=0 paragraph is a bit fiddly but not wrong. No circularity, no free parameters, no gaps in the written proofs.\n\nThis is for people who track Laplacian partial sums or matching/cover parameters in spectral graph theory. A serious referee will verify the case splits in an afternoon and accept. I would cite the statements when I need the refined bounds, and I would send it to peer review without hesitation.","headline":"Clean proofs of Lew’s two refinements of Brouwer; short, correct, and ready for the literature.","tokens_in":8898,"tokens_out":458,"would_cite":true,"duration_ms":5221,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50"],"pacs":[],"model":"grok-4.5","headline":"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.","keywords":["Laplacian eigenvalue sums","matching number","vertex-cover number","partial spectral sums","spectral graph theory","graph spectra","Laplacian matrix"],"falsifier":"Take any concrete graph with known matching number \nu (for instance a disjoint union of triangles plus a matching) and compute its ordered Laplacian spectrum; if for some k with 2\nu ≤ k ≤ n-2 the partial sum ever exceeds the edge count plus k\nu, the matching bound is false.","tokens_in":9038,"feed_emoji":"📈","tokens_out":910,"duration_ms":22346,"temperature":0.7,"pith_summary":"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.","feed_headline":"Matching and cover numbers tighten Laplacian eigenvalue sums","feed_subtitle":"Two parameter-dependent strengthenings of a classical spectral bound are proved and shown sharp on natural graphs.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["Analogous strengthenings may exist for other classical parameters such as arboricity, degeneracy or clique cover number.","The case division at k = 2\nu 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."],"forward_implications":["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."],"fun_headline_variants":["Matching number caps k-largest Laplacian sums","Vertex cover tightens Laplacian eigenvalue bounds","Lew conjectures on Laplacian sums settled","Matching and cover control spectral Laplacian sums","Brouwer proves two matching-cover Laplacian bounds"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Matching number caps k-largest Laplacian sums","Vertex cover tightens Laplacian eigenvalue bounds","Lew conjectures on Laplacian sums settled","Matching and cover control spectral Laplacian sums","Brouwer proves two matching-cover Laplacian bounds"]},"model":"grok-4.5","effort":"low","cost_usd":0.003404,"raw_usage":{"total_tokens":1080,"prompt_tokens":721,"num_sources_used":0,"completion_tokens":48,"cost_in_usd_ticks":34040000,"prompt_tokens_details":{"text_tokens":721,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":311,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":721,"tokens_out":48,"duration_ms":3019,"temperature":1.0,"reasoning_tokens":311,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T15:32:22.748369+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Take any concrete graph with known matching number \nu (for instance a disjoint union of triangles plus a matching) and compute its ordered Laplacian spectrum; if for some k with 2\nu ≤ k ≤ n-2 the partial sum ever exceeds the edge count plus k\nu, the matching bound is false.","supporting_citations":[],"review_version":2}