
Ramanujan graph
Signing a graph to have small magnitude eigenvalues ★★
Conjecture If
is the adjacency matrix of a
-regular graph, then there is a symmetric signing of
(i.e. replace some
entries by
) so that the resulting matrix has all eigenvalues of magnitude at most
.






Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing
