Spectral lower bounds for the orthogonal and projective ranks of a graph (Q2323822)

Summary: 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 [``Spectral lower bounds on the quantum chromatic number'', J. Comb. Theory, Ser. A 168, 338--347 (2019; \url{doi:10.1016/j.jcta.2019.06.008})], 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\).