# 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

-

## 1 Answer

The second reference you give (Cameron), the published version of which can be viewed at http://www.combinatorics.org/Volume_14/PDF/v14i1r81.pdf, claims that this is unsolved. Note however that they don't include the "only if" part of the definition you give. In other words, vectors are allowed to be orthogonal even if the vertices are not adjacent (and similarly for the unitary matrices). It seems that every paper has a different definition.

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)}$.

-
As far as I can understand, Simone Severini is one of the author of that paper. So probably he knows very well what you are saying and just asking help to solve his own conjecture. –  Valerio Capraro Nov 2 '11 at 16:07
Thanks Dan for your interest on this question! Yes, what Valerio correctly points out, I know the above paper. But good news! The relaxed version of the conjecture is now solved. Please give a look at arxiv.org/abs/1106.0712 Kochen-Specker Sets and the Rank-1 Quantum Chromatic Number Giannicola Scarpa, Simone Severini Thanks a lot.. –  Simone Severini Nov 3 '11 at 11:03