A Ramanujan graph is a connected 
-regular graph whose adjacency
eigenvalues other than 
and 
have absolute value at most 
. The eigenvalue 
occurs for connected bipartite regular graphs and is excluded as a trivial eigenvalue.
For a nonbipartite graph only 
is excluded.
Xu (2026) reported a deterministic polynomial-time algorithm that signs every bipartite graph of maximum vertex degree 
so that its signed adjacency
matrix has operator norm strictly less than
. This establishes the bipartite
case of the Bilu-Linial signing conjecture.
Xu (2026) acknowledges ChatGPT assistance with the algorithm
and proof.
