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^{†}{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$.

Improved proof of lower bound on orthogonal rank (Theorem 4); authors appreciate comments