Pith. sign in

REVIEW 4 minor 2 cited by

An Improved Upper Bound for the Bilu-Linial Conjecture via Interlacing Families

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

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

Pith's one-line read Every graph of maximum degree d has a signing whose signed adjacency spectrum lies in an interval of width 2√(3(d−1)).

desk verdict 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. read the letter →

arxiv 2606.28797 v2 pith:ZHQ7PBVZ submitted 2026-06-27 math.CO

Zhiqiang Xu , Xinyue Zhang This is my paper · ORCID
classification math.CO MSC 05C5005C3115A18
keywords Bilu–LinialconjecturesignedadjacencymatrixinterlacingfamiliesmixedcharacteristicpolynomialsmatchingpolynomialRamanujangraphs2-liftsspectralradius
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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 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.

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.

minor comments (4)
  1. 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.
  2. 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.
  3. 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.
  4. 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: self-contained derivation from external interlacing and mixed-characteristic results of Marcus–Spielman–Srivastava and Bownik, with an independent combinatorial identification of the expected mixed characteristic polynomial.

full rationale

The central claim (Theorem 1.5) is obtained by applying the interlacing-family existence statement (Lemma 2.6, from Bownik/MSS) to the random block-diagonal matrices Xe built from independent random signs, then shifting the resulting root bound via Bownik’s block-diagonal comparison (Theorem 2.8) and the operator-norm inequality (Lemma 2.7). The only new analytic step is the upper bound on maxroot(μ[Ye : e ∈ E]) given in Lemma 3.1; that bound follows from the explicit coefficient-wise identification (Lemma 3.2) of 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 HG, whose roots are controlled by the classical path-tree estimate (Lemma 2.15). The identification itself is proved by two elementary bijections (Lemmas 3.3–3.4) that extract coefficients of the determinantal generating function P(x,z) and match them to matchings in HG; both bijections are written out in full and do not rely on any prior result of the present authors. The non-regular reduction is the standard induced-subgraph embedding into a d-regular graph. All load-bearing external theorems are due to Marcus–Spielman–Srivastava or Bownik; the two self-citations ([6],[7]) appear only as historical remarks on interlacing methods and are never invoked in the argument. Consequently the derivation does not reduce to its own inputs by construction, by fitting, or by self-citation.

Assumptions & free parameters 0 free parameters · 4 assumptions · 1 invented entities

The paper rests entirely on standard spectral-graph-theory facts and on three previously published theorems (MSS interlacing, mixed-characteristic root bounds, Bownik’s block comparison). No free parameters are fitted; the only new combinatorial object is the auxiliary (4,d)-biregular graph used as an intermediate device.

assumptions (4)
  • standard math Matching polynomials of graphs are real-rooted and their roots are bounded by the spectral radius of any path tree (Godsil).
    Invoked via Theorem 2.12 and Lemma 2.15 to convert the mixed-characteristic root bound into a concrete numerical estimate.
  • standard math The mixed characteristic polynomials of independent random PSD matrices form an interlacing family (MSS / Brändén / Bownik).
    Lemma 2.5–2.6 supply the existence of a signing whose mixed characteristic root is at most that of the expectation.
  • standard math For block-diagonal PSD matrices with constant block traces, the mixed-characteristic root of any single block is at most the full root minus the sum of the other traces (Bownik, Theorem 2.8).
    Used in (3.12) to pass from the 2n-dimensional matrices Xσe to the n-dimensional summands aσe(aσe)T and bσe(bσe)T.
  • domain assumption Every graph of maximum degree d is an induced subgraph of some d-regular graph (standard reduction).
    Applied at the end of the proof of Theorem 1.5 to remove the regularity hypothesis.
invented entities (1)
  • Auxiliary (4,d)-biregular graph HG
    purpose: Serves as the combinatorial object whose matching polynomial coincides with the expected mixed characteristic polynomial after a change of variables.
    Constructed explicitly in (3.27)–(3.29) by duplicating the vertex set and attaching each original edge to its four endpoint copies; used only as an intermediate device inside the proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Improved Upper Bound for the Bilu-Linial Conjecture via Interlacing Families." pith.science (2026). https://pith.science/paper/ZHQ7PBVZ

@misc{pith2026260628797,
  author       = {Pith},
  title        = {Pith review of: An Improved Upper Bound for the Bilu-Linial Conjecture via Interlacing Families},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZHQ7PBVZ}},
  note         = {Machine review of arXiv:2606.28797}
}
abstract

The Bilu-Linial conjecture asserts that every $d$-regular graph admits a signing $\sigma$ such that the spectral radius of the signed adjacency matrix $A_\sigma$ satisfies $\rho(A_\sigma)\le 2\sqrt{d-1}$. Bilu and Linial also proved the weaker bound $O(\sqrt{d\log^3 d})$ for graphs of maximum degree $d$. Marcus, Spielman, and Srivastava confirmed the conjecture in the case of $d$-regular bipartite graphs. In this paper, we prove that every graph of maximum degree $d$ has a signing $\sigma$ such that $$\rho(A_\sigma)\le 2\sqrt{3(d-1)}.$$ This removes the polylogarithmic factor from the estimate of Bilu and Linial and gives an explicit $2\sqrt{3(d-1)}$ two-sided spectral bound. The proof builds on the method of interlacing polynomials introduced by Marcus, Spielman, and Srivastava, together with results on mixed characteristic polynomials established by Marcus, Spielman, and Srivastava and by Bownik.

Figures

Figures reproduced from arXiv: 2606.28797 by the authors.

Figure 1
Figure 1. An illustration of the auxiliary bipartite graph [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Signed circulants at the Ramanujan bound

    math.CO 2026-07 accept novelty 6.0 of 10

    All signings that make every quadrilateral of C_n(1,2) unbalanced have spectral radius exactly 2√2 or 2√(cos²(π/n)+cos²(2π/n)), the latter conjecturally minimal.

  2. Parity families and a kernel-averaged L-function for near-Ramanujan signings

    math.CO 2026-07 reject novelty 6.0 of 10

    A parity-family averaging identity reduces the signed-spectral-radius problem to walk counting and yields claimed ε-versions of Bilu-Linial for dilute graphs, but the main theorems' final constant extraction is arithm...

Reference graph

Works this paper leans on

19 extracted references · 2 linked inside Pith · cited by 2 Pith papers

  1. [1]

    Y. Bilu, N. Linial,Lifts, discrepancy and nearly optimal spectral gap, Combinatorica26(2006), no. 5, 495–519

    2006

  2. [2]

    Bownik,The Kadison–Singer problem, Frames and Harmonic Analysis, 63–92, Contemp

    M. Bownik,The Kadison–Singer problem, Frames and Harmonic Analysis, 63–92, Contemp. Math., 706, Amer. Math. Soc., Providence, RI, 2018

    2018

  3. [3]

    Bownik,Selector form of Weaver’s conjecture and frame sparsification, arXiv preprint arXiv:2405.18235, 2024

    M. Bownik,Selector form of Weaver’s conjecture and frame sparsification, arXiv preprint arXiv:2405.18235, 2024

    arXiv 2024

  4. [4]

    Bownik,On akemann–weaver conjecture, Adv

    M. Bownik,On akemann–weaver conjecture, Adv. Math.487(2026), 110772

    2026

  5. [5]

    Brändén,Hyperbolic polynomials and the Kadison–Singer problem, arXiv preprint arXiv:1809.03255, 2018

    P. Brändén,Hyperbolic polynomials and the Kadison–Singer problem, arXiv preprint arXiv:1809.03255, 2018

    arXiv 2018

  6. [6]

    Jian-feng Cai, Zhiqiang Xu, Zili Xu,Interlacing polynomial method for the column subset selection problem, Int. Math. Res. Not.2024(2024), no. 9, 7798–7819

    2024

  7. [7]

    Jian-feng Cai, Zhiqiang Xu, Zili Xu,Interlacing polynomial method for matrix approximation via generalized column and row selection, Found. Comput. Math. (2025), 1–50

    2025

  8. [8]

    Chartrand, P

    G. Chartrand, P. Erdős, O. R. Oellermann,How to define an irregular graph, College Math. J.19(1988), no. 1, 36–42

    1988

Show all 19 references
  1. [9]

    M. Cohen,Improved spectral sparsification and Kadison–Singer for sums of higher rank matri- ces, fromhttp://www.birs.ca/events/2016/5-day-workshops/16w5111/videos/watch/ 201608011534-Cohen.html, 2016

    2016

  2. [10]

    C. D. Godsil,Matchings and walks in graphs, J. Graph Theory5(1981), no. 3, 285–297

    1981

  3. [11]

    C. D. Godsil,Algebraic Combinatorics, Chapman and Hall, 1993

    1993

  4. [12]

    O. J. Heilmann, E. H. Lieb,Theory of monomer–dimer systems, Comm. Math. Phys.25 (1972), 190–232

    1972

  5. [13]

    Lubotzky, R

    A. Lubotzky, R. Phillips, P. Sarnak,Ramanujan graphs. Combinatorica8(1988), no. 3, 261–277

    1988

  6. [14]

    König,Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936

    D. König,Theorie der endlichen und unendlichen Graphen, Akademische Verlagsgesellschaft, Leipzig, 1936. Reprinted by Chelsea Publishing Company, New York, 1950

    1936

  7. [15]

    A. W. Marcus, D. A. Spielman, N. Srivastava,Interlacing families I: Bipartite Ramanujan graphs of all degrees, Ann. of Math.182(2015), 307–325

    2015

  8. [16]

    A. W. Marcus, D. A. Spielman, N. Srivastava,Interlacing families II: Mixed characteristic polynomials and the Kadison–Singer problem, Ann. of Math.182(2015), 327–350. 18

    2015

  9. [17]

    A. W. Marcus, D. A. Spielman, N. Srivastava,Interlacing families III: Sharper restricted invertibility estimates, Israel J. Math.247(2022), no. 2, 519–546

    2022

  10. [18]

    A. W. Marcus, D. A. Spielman, N. Srivastava,Interlacing families IV: Bipartite ramanujan graphs of all sizes, SIAM J. Comput.47(2018), no. 6, 2488–2509

    2018

  11. [19]

    Zhiqiang Xu, Zili Xu, Ziheng Zhu,Improved bounds in Weaver’s KSr conjecture for high rank positive semidefinite matrices, J. Funct. Anal.285(2023), no. 4, 109978. 19

    2023

Pith tools

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