pith. sign in

arxiv: 1806.02734 · v3 · pith:BVLLZXVGnew · submitted 2018-06-07 · 🧮 math.CO · quant-ph

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

classification 🧮 math.CO quant-ph
keywords lowerboundsboundchromaticnumberorthogonalrankspectral
0
0 comments X
read the original 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.