Inertia, Independence and Expanders

Abstract

Let $G$ be a graph on $n$ vertices, independence number $\hat{I}\pm (G)$, Lovász theta function $\vartheta (G)$, and Shannon capacity $\hat{I}˜(G)$. We define $n_{\ge 0}(G)$ to be the minimum number of non-negative eigenvalues taken over all Hermitian weighted adjacency matrices of $G$. It is well known that $\hat{I}\pm (G)\le \hat{I}˜(G)\le \vartheta (G)$ and $\hat{I}\pm (G)\le n_{\ge 0}(G)$. Continuing a long line of work, we investigate the relationships between $\hat{I}\pm (G)$, $\vartheta (G)$, $\hat{I}˜(G)$, and $n_{\ge 0}(G)$. We prove a conjecture of Kwan and Wigderson, showing that for every integer $k$, there exists a graph $G$ with $\hat{I}\pm (G)\le 2$ and $n_{\ge 0}(G)\ge k$. In addition, we prove that for every integer $k$, there exists a graph $G$ with $\hat{I}˜(G)\le 3$ and $n_{\ge 0}(G)\ge k$. Both results rely on a new observation: if the complement of $G$ contains a good spectral expander, then $n_{\ge 0}(G)$ must be large. We also show that $\vartheta (G)$ can be exponentially larger than $n_{\ge 0}(G)$, improving a recent result of Ihringer.

15 pages. v2 adds a discussion on Shannon capacity; this is the submitted version