Id: arxiv/2609.17551 Url: https://arxiv.org/abs/2609.17551 Tags: math.CO Score: 0 Title: A $\sqrt{2}$-Approximation to the Bilu-Linial Conjecture Domain: math.CO Source: arxiv Authors: Zejun Huang Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-16 Page: https://delphi.science/r/arxiv/2609.17551 Bilu and Linial conjectured that if $d\ge 2$, then every $d$-regular graph $G$ has an edge signing $σ:E(G)\to\{-1,1\}$ such that its signed adjacency matrix $A_σ$ satisfies the Ramanujan bound \begin{equation*} ρ(A_σ)\le 2\sqrt{d-1} \end{equation*} and they proved that \begin{equation*} ρ(A_σ)=O\!\left(\sqrt{d\log^3 d}\right). \end{equation*} Using a method of interlacing polynomials, Marcus, Spielman, and Srivastava confirmed one side of this conjecture that there is a signing $σ$ for which \[ λ_{\max}(A_σ)\le 2\sqrt{d-1}. \] By constructing an auxiliary bipartite graph from a balanced…