Spectral Lower Bounds for the Orthogonal and Projective Ranks of a Graph

Abstract

The orthogonal rank of a graph $G=(V,E)$ is the smallest dimension $\xi$ such that there exist non-zero column vectors $x_v\in\mathbb{C}^\xi$ for $v\in V$ satisfying the orthogonality condition $x_v^\dagger x_w=0$ for all $vw\in E$.   We prove that many spectral lower bounds for the chromatic number, $\chi$, are also lower bounds for $\xi$. This result complements a previous result by the authors, in which they showed that spectral lower bounds for $\chi$ are also lower bounds for the quantum chromatic number $\chi_q$.  It is known that the quantum chromatic number and the orthogonal rank are incomparable.  

We conclude by proving an inertial  lower bound for the projective rank $\xi_f$, and conjecture that a stronger inertial lower bound for $\xi$ is also a lower bound for $\xi_f$.