{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-16","reactions":{}}