OP-00400 Solution claimed

Optimal spectral signings of regular graphs

Let $d \ge 2$ and let $G = (V, E)$ be a finite simple $d$-regular graph. A signing of $G$ is a map $s : E \to \{-1, 1\}$, and its signed adjacency matrix $A_s$ has entries $(A_s)_{uv} = s(\{u, v\})$ for $\{u, v\} \in E$ and $0$ otherwise. The eigenvalues of $A_s$ are the new eigenvalues of the 2-lift of $G$ defined by $s$, and $2\sqrt{d-1}$ is the Ramanujan bound. Bilu and Linial proved that every graph of maximum degree $d$ has a signing whose signed adjacency matrix has spectral radius $O(\sqrt{d \log^3 d})$. Marcus, Spielman and Srivastava proved that every $d$-regular graph has a signing all of whose eigenvalues are at most $2\sqrt{d-1}$; when $G$ is bipartite the spectrum of $A_s$ is symmetric about $0$, so this bounds every $|\lambda|$.

Problem. Does every such graph admit a signing $s$ for which every eigenvalue $\lambda$ of $A_s$ satisfies $|\lambda| \le 2\sqrt{d-1}$? Both ends of the spectrum must satisfy the bound.

Source: Bilu and Linial (2006), Conjecture 3.1 (arXiv 2003); see also their note in Combinatorics, Probability and Computing (2004).

Imported from github.com/MColbrook/AIM.

Classification

Primary: CO — Combinatorics
Secondary: SP
Keywords: AIM Open Applied Problems, graph lifts, Ramanujan graphs, signed graphs

References

@article{bilu2006,
  author        = {Bilu, Yonatan and Linial, Nathan},
  title         = {Lifts, discrepancy and nearly optimal spectral gap},
  journal       = {Combinatorica},
  volume        = {26},
  number        = {5},
  year          = {2006},
  pages         = {495--519},
  doi           = {10.1007/s00493-006-0029-7},
  eprint        = {math/0312022},
  archivePrefix = {arXiv},
}
@article{bilu2004,
  author  = {Bilu, Yonatan and Linial, Nathan},
  title   = {Ramanujan signing of regular graphs},
  journal = {Combin. Probab. Comput.},
  volume  = {13},
  number  = {6},
  year    = {2004},
  pages   = {911--912},
  doi     = {10.1017/S0963548304006509},
}
@article{marcus2015,
  author        = {Marcus, Adam W. and Spielman, Daniel A. and Srivastava, Nikhil},
  title         = {Interlacing families {I}: {B}ipartite {R}amanujan graphs of all degrees},
  journal       = {Ann. of Math. (2)},
  volume        = {182},
  number        = {1},
  year          = {2015},
  pages         = {307--325},
  doi           = {10.4007/annals.2015.182.1.7},
  eprint        = {1304.4132},
  archivePrefix = {arXiv},
}
@misc{aim-bilu-linial-signing,
  author       = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
  title        = {{Optimal spectral signings of regular graphs}},
  howpublished = {AIM --- Open Applied Problems, GitHub repository},
  year         = {2026},
  url          = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/214-bilu-linial-signing.md},
  note         = {Entry 214 at commit a153f46, 2026-10-13},
}

Resolution claims

A 3-regular counterexample to the Bilu--Linial signing conjecture v1 arXiv ↗ AI-Verified

Zhiqiang Xu

We construct a finite connected simple cubic graph $F$ such that every signing of its edges yields a signed adjacency matrix with an eigenvalue outside $[-2\sqrt2,2\sqrt2]$. This disproves the Bilu--Linial signing conjecture for general regular graphs. The graph $F$ is not Ramanujan, and the conjecture restricted to Ramanujan base graphs remains open.

Counterexample · not verified · fidelity not established · posted on arXiv 29 Sep 2026

Status history

When	Change	By	Reason
2026-10-15	Needs verification → Solution claimed	—	Recorded here: arXiv:2609.15591v4.

Citing this problem

This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.

OP-00400, "Optimal spectral signings of regular graphs", clopen.solutions.