Interlacing families and the Hermitian spectral norm of digraphs
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 resolv...
Saved in:
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/146676 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Nanyang Technological University |
| Language: | English |
| Summary: | 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. |
|---|