Inertia, Independence and Expanders

Let G be a graph on n vertices, independence number $α(G)$, Lovász theta function ϑ(G), and Shannon capacity $Θ(G)$. We define n≥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 α(G) ≤ Θ(G) ≤ ϑ(G) and α(G) ≤ n≥0(G). Continuing a long line of work, we investigate the relationships between $ α(G) $, ϑ(G), $Θ(G)$, and n≥ 0(G). We prove a conjecture of Kwan and Wigderson, showing that for every integer k, there exists a graph G with α(G) ≤ 2 and n≥ 0(G) ≥ k. In addition, we prove that for every integer k, there exists a graph G with Θ(G) ≤ 3 and n≥ 0(G) ≥ k. Both results rely on a new observation: if the complement of G contains a good spectral expander, then n≥ 0(G) must be large. We also show that ϑ(G) can be exponentially larger than n≥ 0(G), improving a recent result of Ihringer.