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