Inertia, independence and expanders

Abstract Let be a graph on vertices, independence number , Lovász theta function and Shannon capacity . We define to be the minimum number of non‐negative eigenvalues taken over all Hermitian weighted adjacency matrices of . It is well known that and . Continuing a long line of work, we investigate the relationships between , , and . We prove a conjecture of Kwan and Wigderson, showing that for every integer , there exists a graph with and . In addition, we prove that for every integer , there exists a graph with and . Both results rely on a new observation: if the complement of contains a good spectral expander, then must be large. Moreover, we show that the multiplicative gap between and can be . We also show that can be exponentially larger than , improving a recent result of Ihringer.