MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## From orthogonal representations of graphs to orthogonal matrix representations of graphs

An orthogonal representation [1] of a graph $G=(V,E)$ on $n$ vertices ${1,2,...,n}$ is an assignment of (complex) unit vectors $v_{1},v_{2},...,v_{n}$ to the vertices of $G$ such that $\langle v_{i},v_{j}\rangle =0$ if and only if ${i,j}\in E(G)$.

An orthogonal matrix representation (see, e.g., [2]) of $G$ is an assignment of unitary matrices $U_{1},U_{2},...,U_{n}$ to the vertices of $G$ such that $[U_{i}^{\dagger }U_{j}]_{k,k}=0$, for every $k$, if and only if $% {i,j}\in E\left( G\right)$.

Is it true that if there is an orthogonal representation of a certain dimension then there is always an orthogonal matrix representation of the same dimension?

[1] L. LovĂˇsz, On the Shannon Capacity of a Graph, IEEE Trans. Inf. Theory, 25 (1):1-7 (1979).

[2] P. J. Cameron, A. Montanaro, M. Newmann, S. Severini, A. Winter, On the quantum chromatic number of a graph, http://arxiv.org/abs/quant-ph/0608016

-

Their Proposition 7 gives that an orthogonal representation with all vector entries having modulus one ($\xi'$) implies the existence of an orthogonal matrix representation ($\chi_q^{(1)}$), which in turn implies the existence of a orthogonal representation without the modulus-one restriction ($\xi$). Specifically, $\xi \le \chi_q^{(1)} \le \xi'$. In their conclusion they mention that it is an open problem whether there is a separation between $\xi'$ and $\xi$. If there is no separation then $\xi=\chi_q^{(1)}=\xi'$, otherwise I suppose it would be a further task to determine whether there is a separation between $\xi$ and $\chi_q^{(1)}$.