Why is the smallest dimension for which there exists an orthogonal representation bounded by the coloring of the complement?

41 Views Asked by At

In my book about graph theory it quite casually states that for the smallest dimension $d$ for which there exists an orthonormal representation of a graph $G$ it holds that $d \leq \chi(\bar{G})$ (where $\chi(\bar{G})$ is the coloring of the graph $\bar{G}$.

An orthonormal representation of a graph $G$ is a set of unit vectors $\{u_1, \dots u_n\} \subseteq \mathbb{R}^d $ with $u_i^Tu_j = 0$ when $\{i,j\}\in \bar{E}$.

How does this work?

1

There are 1 best solutions below

0
On BEST ANSWER

Say $S\subset V$ is the maximum stable set of $G$. When we can form an orthogonal representation in the following way: for all $i,j\in S$ we need $u_i^Tu_j =0$ because $\{i,j\}\in \bar{E}$. Say $S = \{v_1, \dots v_{|S|}\}$, set $u_{v_k} = e_k$ (so the canononical base vector with all zeros except on the $k^{th}$ component.

Then this is an orthagonal representation of $G$, but $$\min\{d |\{u_1, \dots u_n\}\in \mathbb{R}^d \text{ orthogonal representation }G \} \leq |S| =\alpha(G) = \omega(\bar{G}) \leq \chi(\bar{G})$$

and therfore smallest dimension for which there exists an orthogonal representation bounded by the coloring of the complement.