MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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,

share|cite|improve this question

The second reference you give (Cameron), the published version of which can be viewed at, 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)}$.

share|cite|improve this answer
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 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.