PreprintarXiv licencearXiv
A √2-Approximation to the Bilu-Linial Conjecture
Abstract
Bilu and Linial conjectured that if d≥ 2, then every d-regular graph G has an edge signing σ:E(G)→{−1,1} such that its signed adjacency matrix Aσ satisfies the Ramanujan bound ρ(Aσ)≤ 2√(d−1) and they proved that ρ(Aσ)=O (√(dlog3 d)). 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σ)≤ 2√(d−1). By constructing an auxiliary bipartite graph from a balanced orientation of G and applying a bipartite signing argument, we prove that every finite simple graph G of maximum degree d≥ 3 admits an edge signing σ such that ρ(Aσ) ≤ 4√(⌈ d/2⌉−1) ≤ 2√(2(d−1)). Thus we obtain a bound within a factor at most √2 of the conjectured Ramanujan bound.
Related
- A 3-regular counterexample to the Bilu--Linial signing conjecture
- Improved Bounds for the Bilu-Linial Conjecture via Spectral Recovery from Mixed Determinantal Polynomials
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- Kadison--Singer partitions and Bilu--Linial graph signings in polynomial time
- A counterexample to the determinant approximation conjecture
BibTeX
@misc{huang20262approximation,
title = {{A $\sqrt2$-Approximation to the Bilu-Linial Conjecture}},
author = {Zejun Huang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.17551},
eprint = {2609.17551},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.17551},
}
RIS
TY - UNPB
TI - A √2-Approximation to the Bilu-Linial Conjecture
AU - Zejun Huang
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.17551
UR - https://arxiv.org/abs/2609.17551
AB - Bilu and Linial conjectured that if d≥ 2, then every d-regular graph G has an edge signing σ:E(G)→{−1,1} such that its signed adjacency matrix A_σ satisfies the Ramanujan bound ρ(A_σ)≤ 2√(d−1) and they proved that ρ(A_σ)=O (√(dlog^3 d)). 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_σ)≤ 2√(d−1). By constructing an auxiliary bipartite graph from a balanced orientation of G and applying a bipartite signing argument, we prove that every finite simple graph G of maximum degree d≥ 3 admits an edge signing σ such that ρ(A_σ) ≤ 4√(⌈ d/2⌉−1) ≤ 2√(2(d−1)). Thus we obtain a bound within a factor at most √2 of the conjectured Ramanujan bound.
ER -