The Bilu-Linial conjecture is a question about graphs, which are mathematical structures made of nodes connected by edges. In this setting, each edge can be "signed," meaning labeled with either +1 or -1. This signing changes how the graph behaves algebraically, specifically through a matrix that encodes which nodes are connected and with what sign. The conjecture says that for any sufficiently regular graph (one where every node has the same number of connections), you can always find a signing that keeps the largest eigenvalue of this matrix within a specific bound called the Ramanujan bound. Eigenvalues are numbers that capture important structural properties of matrices, and smaller eigenvalues here correspond to better-behaved, more "random-like" graphs with good connectivity properties.
Previous progress on this conjecture was partial. Bilu and Linial themselves proved a bound that was much larger than conjectured, off by factors involving the logarithm of the degree. A celebrated 2015 result by Marcus, Spielman, and Srivastava used a clever technique called interlacing polynomials to confirm half the conjecture, showing you can always find a signing that controls the largest eigenvalue from above. However, controlling both the largest and smallest eigenvalues simultaneously, which is what the spectral radius (the focus of the full conjecture) requires, remained open.
This paper proves that every graph with maximum degree d has a signing whose spectral radius is within a factor of the square root of 2 of the conjectured Ramanujan bound. The authors achieve this by constructing a related bipartite graph from a balanced orientation of the original graph, then applying a signing argument to that auxiliary structure. A balanced orientation means directing edges so that each node has roughly equal numbers of incoming and outgoing edges. This geometric and combinatorial trick allows them to transfer and strengthen existing results, landing within striking distance of the full conjecture with a clean and significantly improved bound.