TOPICS
Search

Bilu-Linial Signing Conjecture

The Bilu-Linial signing conjecture (Bilu and Linial 2004) states that every finite simple d-regular graph G has a graph edge signing sigma:E(G)->{-1,1} for which the signed adjacency matrix A_sigma satisfies

||A_sigma||<=2sqrt(d-1).

Equivalently, all eigenvalues of A_sigma lie in the interval [-2sqrt(d-1),2sqrt(d-1)].

Xu (2026) gave an explicit but enormous connected simple cubic graph F for which no signing satisfies the conjectured bound. The construction starts with a triangle graph joined to three complete binary trees of height 62. Copies of this rooted seed are combined by 61 levels of binary joins, and three resulting rooted graphs are joined to a central vertex. Within each seed, the leaves are placed in a specified order, and each consecutive triple is joined to two new vertices. Its vertex count is

|V(F)|=3·2^(126)+3·2^(62)-2=255211775190703847611366013629108322302.

The construction therefore refutes the conjecture, although the restricted question in which the unsigned graph is a Ramanujan graph remains open. Xu (2026) reports that ChatGPT assisted in finding the counterexample and developing its proof. As of Sep. 22, 2026, independent specialist review had not been reported.

See also

Adjacency Matrix, Cubic Graph, Matrix Norm

Explore with Wolfram|Alpha

References

Bilu, Y. F. and Linial, N. "Ramanujan Signings of Regular Graphs." Combin. Probab. Comput. 13, 911-912, 2004.Bilu, Y. F. and Linial, N. "Lifts, Discrepancy and Nearly Optimal Spectral Gap." Combinatorica 26, 495-519, 2006. https://doi.org/10.1007/s00493-006-0029-7.Xu, Z. "A 3-Regular Counterexample to the Bilu-Linial Signing Conjecture." 18 Sep 2026. https://arxiv.org/abs/2609.15591.

Cite this as:

Weisstein, Eric W. "Bilu-Linial Signing Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Bilu-LinialSigningConjecture.html

Subject classifications