Bilu-Linial Signing Conjecture

The Bilu-Linial signing conjecture (Bilu and Linial 2004) states that, for every integer , every finite simple -regular graph has a graph edge signing for which the signed adjacency matrix satisfies

(1)

Equivalently, all eigenvalues of lie in the interval .

Xu (2026a) gave an explicit but enormous connected simple cubic graph for which no signing satisfies the conjectured bound. The construction starts with a triangle graph on , , and , and an additional root vertex joined to . Three disjoint complete binary trees of height 62 are attached by their roots to , , and , respectively. 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

(2)

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

For bipartite simple graphs of maximum vertex degree , Xu (2026b) reported a deterministic polynomial-time algorithm producing a signing with

(3)

In particular, this gives the conjectured signing bound for bipartite regular graphs. It does not restore the conjecture for general nonbipartite graphs. Xu (2026b) credits ChatGPT with assistance in developing the algorithm and proof, which he states that he verified.