Interlacing families and the Hermitian spectral norm of digraphs

Abstract

It is proved that for any finite connected graph $G$, there exists an orientation of $G$ such that the spectral radius of the corresponding Hermitian adjacency matrix is smaller or equal to the spectral radius of the universal cover of $G$ (with equality if and only if $G$ is a tree). This resolves a problem proposed by Mohar. The proof uses the method of interlacing families of polynomials that was developed by Marcus, Spielman, and Srivastava in their seminal work on the existence of infinite families of Ramanujan graphs.