Ramanujan graph


Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

Conjecture   If $ A $ is the adjacency matrix of a $ d $-regular graph, then there is a symmetric signing of $ A $ (i.e. replace some $ +1 $ entries by $ -1 $) so that the resulting matrix has all eigenvalues of magnitude at most $ 2 \sqrt{d-1} $.

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

Syndicate content