{"id":"60e5907a-749d-423b-b81c-058137770bae","arxiv_id":"2606.28797","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Every graph of maximum degree d admits a signing σ with ρ(A_σ) ≤ 2√(3(d-1)).","lead":"Every graph of maximum degree d has an edge signing whose signed adjacency matrix has spectral radius at most 2√(3(d-1)). This removes the polylog factor from Bilu–Linial’s earlier bound and supplies an explicit two-sided spectral guarantee useful for constructing Ramanujan graphs by repeated 2-lifts.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly isolates Lemma 3.2 as the sole novel combinatorial step on which the root bound of Lemma 3.1 (and therefore the constant 2√(3(d−1))) depends. Direct inspection of the coefficient extraction and the two bijections confirms that the step is sound; the remainder of the argument is a faithful application of established interlacing and matching-polynomial machinery. No free parameters, circular citations, or unstated regularity assumptions affect the claim. The manuscript therefore supplies a complete, self-contained existence proof that improves the classical Bilu–Linial estimate, and the ACCEPT verdict stands.","tokens_in":17130,"tokens_out":571,"duration_ms":21911,"concrete_test":"For the complete graph K_4 (d=3) explicitly expand both sides of the identity in Lemma 3.2: compute the mixed characteristic polynomial μ[Ye] by the product formula (3.18) and the matching polynomial of the resulting (4,3)-biregular HG by enumeration of matchings; verify that the coefficients of x^{nd/2−2n} μ(x^{2}) and MHG(x) agree up to degree 12. Any mismatch would falsify the combinatorial correspondence.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 1.5) rests on the existence of a signing whose two-sided spectral radius is controlled by maxroot of the expected mixed characteristic polynomial μ[Ye : e ∈ E]. Lemma 3.2 identifies that polynomial (after the change of variables x ↦ x^{2} and the prefactor x^{nd/2−2n}) with the matching polynomial of the auxiliary (4,d)-biregular graph HG. The identification is proved by extracting coefficients of P(x,z) via injective maps ϕ : F → V×{1,2} (Lemma 3.3) and exhibiting an explicit bijection between those maps and the matchings in HG that cover exactly the left vertices corresponding to F (Lemma 3.4). Both bijections are written out in full and appear free of gaps or hidden assumptions. All subsequent steps (interlacing via Lemma 2.6, the block-diagonal root shift of Theorem 2.8, the operator-norm bound of Lemma 2.7, and the path-tree estimate of Lemma 2.15) invoke only published results of Marcus–Spielman–Srivastava and Bownik. The non-regular reduction is the standard induced-subgraph embedding into a d-regular graph. Consequently no load-bearing flaw is present.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper proves that every graph of maximum degree d (d≥2) admits a signing σ such that the spectral radius of the signed adjacency matrix satisfies ρ(A_σ)≤2√(3(d-1)). This improves Bilu–Linial’s O(√(d log^{3} d)) bound by removing the polylog factor and supplies an explicit two-sided constant. The argument constructs independent random rank-one matrices X_e from random edge signs, applies the interlacing property of mixed characteristic polynomials (Lemma 2.6) to obtain a signing whose mixed-characteristic largest root is at most that of the expected matrices Y_e, invokes Bownik’s block-diagonal comparison (Theorem 2.8) to control both dI+A_σ and dI-A_σ, and identifies the expected mixed characteristic polynomial (after the substitution x↦x^{2} and a monomial prefactor) with the matching polynomial of an auxiliary (4,d)-biregular graph H_G (Lemma 3.2). The largest root of the latter is then bounded by the path-tree spectral-radius estimate of Lemma 2.15. The non-regular case is reduced to the regular case by the standard induced-subgraph embedding into a d-regular graph.","tokens_in":17431,"tokens_out":894,"duration_ms":7480,"significance":"The result is a clear quantitative advance on a well-known open problem: it replaces Bilu–Linial’s polylogarithmic factor by an explicit constant 2√3 while remaining fully two-sided, thereby strengthening the only previously available general bound. The proof is self-contained once the published interlacing, mixed-characteristic and matching-polynomial tools of Marcus–Spielman–Srivastava and Bownik are granted; the only original combinatorial step (the coefficient extraction and bijection of Lemmas 3.3–3.4) is written out in full. While the constant √3 is still larger than the conjectured Ramanujan value 1, the paper supplies a concrete, checkable improvement and correctly identifies the two places (the path-tree bound for H_G and the block-diagonal comparison) where further sharpening may be possible. The derivation is free of free parameters and of circular normalizations.","major_comments":[],"minor_comments":[{"comment":"In the statement of Lemma 3.2 the prefactor is written x^{nd/2-2n}; a short parenthetical remark that |L|=nd/2 for a d-regular graph on n vertices would make the exponent immediately transparent.","section":null},{"comment":"Figure 1 is helpful but the caption could explicitly note that the red edges illustrate the four neighbours of a left vertex and the blue edges the d neighbours of a right vertex, matching the (4,d)-biregularity claim.","section":null},{"comment":"Section 4 correctly flags the two natural improvement points; a one-sentence quantitative comparison of 2√(3(d-1)) with the original Bilu–Linial O(√(d log^{3} d)) for moderate d (say d=10) would help non-specialist readers gauge the gain.","section":null},{"comment":"A few typographical inconsistencies appear (e.g., “Inthispaper” missing spaces in the introduction, occasional missing spaces after commas in displayed equations). A light copy-edit would remove them.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a solid, correctly executed application of the interlacing-family machinery. I see no load-bearing gaps. The constant is not optimal, but the paper does not claim optimality and the improvement over Bilu–Linial is genuine. Suitable for a combinatorial or spectral-graph-theory journal of good standing."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The new theorem is exactly what the abstract claims: every max-degree-d graph has a signing with ρ(A_σ) ≤ 2√(3(d-1)). That is the first explicit two-sided constant for the non-bipartite case and it erases the log^{3}d factor from Bilu–Linial. MSS already gave the one-sided Ramanujan bound; this paper gets both sides at the cost of a √3.\n\nThey do it by packaging both signs into 2n-dimensional block-diagonal matrices X_e, taking the mixed characteristic polynomial, and showing (after x \to x^{2}) that the expected polynomial is the matching polynomial of an auxiliary (4,d)-biregular graph H_G. The two bijections that prove the identification (Lemmas 3.3–3.4) are written out carefully and look correct; the stress-test found no gap and neither did I. Once that is in hand, Bownik’s block comparison, the usual interlacing lemma, and the path-tree bound for biregular graphs finish the argument. The non-regular reduction is the standard embedding into a regular supergraph. Everything is self-contained and rests only on published MSS/Bownik results plus elementary matching-polynomial facts.\n\nThe soft spots are real but modest. The constant √3 is an artifact of the four-neighbor construction; the authors themselves note that a refined block comparison exploiting the rank-one coupling a_e a_eᵀ + b_e b_eᵀ = 2(e_u e_uᵀ + e_v e_vᵀ) might improve it. The path-tree bound for H_G is also not claimed to be sharp. Neither issue breaks the theorem that is proved. Citation pattern is clean; no circularity.\n\nThis is for people who already care about interlacing families or the Ramanujan-lift program. It is a clean incremental advance, not a conceptual leap, but the math is solid and the write-up is complete. I would send it to referees without hesitation and would cite the bound when I need a two-sided estimate that is free of logs.","headline":"Solid, fully written two-sided bound 2√(3(d-1)) that cleanly removes Bilu–Linial’s polylog; the combinatorial identification holds and the constant is the honest price of the method.","tokens_in":18048,"tokens_out":597,"would_cite":true,"duration_ms":5908,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C50","05C31","15A18"],"pacs":[],"model":"grok-4.5","headline":"Every graph of maximum degree d has a signing whose signed adjacency spectrum lies in an interval of width 2√(3(d−1)).","keywords":["Bilu–Linial conjecture","signed adjacency matrix","interlacing families","mixed characteristic polynomials","matching polynomial","Ramanujan graphs","2-lifts","spectral radius"],"falsifier":"Compute the largest root of the expected mixed characteristic polynomial for a small regular graph (for example K_4 or the Petersen graph) both by direct expansion and via the matching polynomial of the associated (4,d)-biregular graph; any discrepancy larger than floating-point error falsifies the identification lemma.","tokens_in":18027,"feed_emoji":"📐","tokens_out":1032,"duration_ms":8843,"temperature":0.7,"pith_summary":"The Bilu–Linial conjecture predicts that any d-regular graph can be signed so that the spectral radius of the signed adjacency matrix is at most the Ramanujan bound 2√(d−1). Earlier work proved a weaker bound that still carried a polylogarithmic factor in d, and a one-sided bound of the optimal size. This paper removes the polylog factor and supplies an explicit two-sided guarantee: every graph of maximum degree d admits a signing whose signed spectrum lies inside [−2√(3(d−1)), 2√(3(d−1))]. The argument uses interlacing families of mixed characteristic polynomials; after a change of variables the expected polynomial is identified with the matching polynomial of an auxiliary (4,d)-biregular graph, whose roots are controlled by the spectral radius of a path tree. The result therefore brings the best unconditional two-sided bound for general graphs within a constant factor of the conjectured optimum and supplies a concrete tool for constructing nearly Ramanujan lifts.","feed_headline":"Signed graphs get a clean two-sided spectral bound","feed_subtitle":"Every max-degree-d graph admits a signing with radius at most 2√(3(d−1)), stripping the old log factors.","key_machinery":"Interlacing families of mixed characteristic polynomials, together with the combinatorial identification that the expected mixed characteristic polynomial of a certain block-diagonal ensemble equals (after substitution x↦x^{2}) the matching polynomial of an auxiliary (4,d)-biregular graph built by doubling the vertex set of G.","core_discovery":"Every graph of maximum degree d (d≥2) admits a signing σ of its edges such that the spectral radius of the signed adjacency matrix satisfies ρ(A_σ) ≤ 2√(3(d−1)). This bound is two-sided, free of logarithmic factors, and holds for non-regular as well as regular graphs.","pith_inferences":["Because the auxiliary graph is built by duplicating vertices, a refined analysis that exploits this two-copy structure might replace the factor 3 by a number closer to 1, narrowing the remaining gap to the Ramanujan bound.","The same block-diagonal mixed-characteristic-polynomial framework could be applied to other signing or orientation problems (for example, discrepancy of edge labelings or spectral expanders with prescribed eigenvalues) where one currently has only one-sided control.","If a matching-polynomial argument can be found that produces a (2,d)-biregular rather than a (4,d)-biregular graph, the resulting bound would become exactly the Bilu–Linial conjecture for general graphs."],"forward_implications":["The best unconditional two-sided spectral bound for signed adjacency matrices of maximum-degree-d graphs improves from O(√(d log³ d)) to the explicit constant 2√(3(d−1)).","Repeated 2-lifts starting from any base graph now produce infinite families whose non-trivial eigenvalues are guaranteed to lie inside an interval of width 2√(3(d−1)).","The same interlacing-plus-matching-polynomial technique immediately yields an explicit two-sided bound for any graph that can be realized as an induced subgraph of a d-regular graph.","The constant 3 appearing under the square root is an artifact of the (4,d)-biregular construction and is therefore a concrete target for further tightening."],"fun_headline_variants":["Max-degree-d graphs admit signings with ρ ≤ 2√(3(d−1))","Log-free bound: every max-degree-d graph has a signing of radius 2√(3(d−1))","Interlacing polynomials give two-sided spectral radius ≤ 2√(3(d−1))","Bilu–Linial improved: signings achieve ρ(A_σ) ≤ 2√(3(d−1)) for degree d","Every graph of max degree d has a signing with clean bound 2√(3(d−1))"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The proof rests on the claim that the expected mixed characteristic polynomial is exactly the matching polynomial of a carefully constructed (4,d)-biregular graph; if that combinatorial correspondence fails, the root bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Max-degree-d graphs admit signings with ρ ≤ 2√(3(d−1))","Log-free bound: every max-degree-d graph has a signing of radius 2√(3(d−1))","Interlacing polynomials give two-sided spectral radius ≤ 2√(3(d−1))","Bilu–Linial improved: signings achieve ρ(A_σ) ≤ 2√(3(d−1)) for degree d","Every graph of max degree d has a signing with clean bound 2√(3(d−1))"]},"model":"grok-4.5","effort":"low","cost_usd":0.006166,"raw_usage":{"total_tokens":1599,"prompt_tokens":761,"num_sources_used":0,"completion_tokens":147,"cost_in_usd_ticks":61660000,"prompt_tokens_details":{"text_tokens":761,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":691,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":761,"tokens_out":147,"duration_ms":5963,"temperature":1.0,"reasoning_tokens":691,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-12T11:16:12.555635+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Compute the largest root of the expected mixed characteristic polynomial for a small regular graph (for example K_4 or the Petersen graph) both by direct expansion and via the matching polynomial of the associated (4,d)-biregular graph; any discrepancy larger than floating-point error falsifies the identification lemma.","supporting_citations":[],"review_version":2}