An inertial upper bound for the quantum independence number of a graph

Abstract

A well known upper bound for the independence number $\alpha (G)$ of a graph $G$, is that \[ α(G) \le n^0 + \min\{n^+ , n^-\}, \] where $(n^{+},n^0,n^{-})$ is the inertia of $G$. We prove that this bound is also an upper bound for the quantum independence number ${\alpha }_q$(G), where ${\alpha }_q(G)\ge \alpha (G)$. We identify numerous graphs for which $\alpha (G)={\alpha }_q(G)$ and demonstrate that there are graphs for which the above bound is not exact with any Hermitian weight matrix, for $\alpha (G)$ and ${\alpha }_q(G)$. This result complements results by the authors that many spectral lower bounds for the chromatic number are also lower bounds for the quantum chromatic number.

updated section on quantum clique number; authors welcome comments