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$.
@article{10_37236_8183,
author = {Pawel Wocjan and Clive Elphick},
title = {Spectral lower bounds for the orthogonal and projective ranks of a graph},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {3},
doi = {10.37236/8183},
zbl = {1419.05136},
url = {http://geodesic.mathdoc.fr/articles/10.37236/8183/}
}
TY - JOUR
AU - Pawel Wocjan
AU - Clive Elphick
TI - Spectral lower bounds for the orthogonal and projective ranks of a graph
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/8183/
DO - 10.37236/8183
ID - 10_37236_8183
ER -
%0 Journal Article
%A Pawel Wocjan
%A Clive Elphick
%T Spectral lower bounds for the orthogonal and projective ranks of a graph
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/8183/
%R 10.37236/8183
%F 10_37236_8183
Pawel Wocjan; Clive Elphick. Spectral lower bounds for the orthogonal and projective ranks of a graph. The electronic journal of combinatorics, Tome 26 (2019) no. 3. doi: 10.37236/8183
