From orthogonal representations of graphs to orthogonal matrix representations of graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T18:08:26Z http://mathoverflow.net/feeds/question/45330 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/45330/from-orthogonal-representations-of-graphs-to-orthogonal-matrix-representations-of From orthogonal representations of graphs to orthogonal matrix representations of graphs Simone Severini 2010-11-08T17:30:53Z 2011-11-16T16:22:12Z <p>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)$. </p> <p>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)$. </p> <p>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?</p> <p>[1] L. Lovász, On the Shannon Capacity of a Graph, IEEE Trans. Inf. Theory, 25 (1):1-7 (1979).</p> <p>[2] P. J. Cameron, A. Montanaro, M. Newmann, S. Severini, A. Winter, On the quantum chromatic number of a graph, <a href="http://arxiv.org/abs/quant-ph/0608016" rel="nofollow">http://arxiv.org/abs/quant-ph/0608016</a></p> http://mathoverflow.net/questions/45330/from-orthogonal-representations-of-graphs-to-orthogonal-matrix-representations-of/79842#79842 Answer by Dan Stahlke for From orthogonal representations of graphs to orthogonal matrix representations of graphs Dan Stahlke 2011-11-02T15:33:52Z 2011-11-02T15:33:52Z <p>The second reference you give (Cameron), the published version of which can be viewed at <a href="http://www.combinatorics.org/Volume_14/PDF/v14i1r81.pdf" rel="nofollow">http://www.combinatorics.org/Volume_14/PDF/v14i1r81.pdf</a>, 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.</p> <p>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)}$.</p>