From orthogonal representations of graphs to orthogonal matrix representations of graphs

2010-11-08T17:30:53Z

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

Answer by Dan Stahlke for From orthogonal representations of graphs to orthogonal matrix representations of graphs

2011-11-02T15:33:52Z

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

From orthogonal representations of graphs to orthogonal matrix representations of graphs - MathOverflow

From orthogonal representations of graphs to orthogonal matrix representations of graphs

Answer by Dan Stahlke for From orthogonal representations of graphs to orthogonal matrix representations of graphs