signed graph

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

\begin{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}$. \end{conjecture}

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

Syndicate content