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