On the definition of the Lovász number and the proof of the sandwich theorem

69 Views Asked by At

The proof of the Lovász Sandwhich theorem, which says that the chromatic number of the complement of a graph $\chi(\bar{G})$ bounds the the Lovász number $\theta(G)$ is given here https://www2.math.ethz.ch/t3/fileadmin/math/ndb/00238/07403/Lovasz_eth_orth1.pdf

The definition given across many sources (also in Lovász's original paper) defines this Lovász number for some orthonormal representation $\left\{u_i:1\leq i \leq n \right\}$ as $$\theta(G)= \min_{c}\max_{1\leq i \leq n}\frac{1}{(c^{T}u_i)^2},$$ with $c$ ranging across all unit vectors.

In particular, in the proof the result of the sandwhich theorem follows from taking the handle vector $c$ to be the $1/\sqrt{k}(e_1+\dots+e_k)$ and associating the representation of $e_j$ to vertex $i$ when it is coloured with colour $j$.

However, in my spectral graph theory course, we are given that this number is defined only for the handle $e_1$, i.e. we define the Lovász number to be the infimum of all orthogonal representations of $\max_{i\in V} \frac{1}{(e_1^{T}u_i)^2}$, with $u_i$ the orthogonal representaion of vertex $i\in V$ and the lecturer told us that this trivially follows since a change of basis is sufficient to use either definition, but I don't see this and thus I don't see how the proof of this inequality follows from my given definition.

1

There are 1 best solutions below

0
On

Suppose that you have an orthogonal representation $\{u_1,\ldots,u_n\}$ and some unit vector $c$. You can find some orthogonal transformation $A$ that sends $c$ to $e_1$. (This is easy: take an orthornomal basis $B_1$ containing $c$ and another orthonormal basis $B_2$ containing $e_1$, and define $A$ by mapping the basis $B_1$ to $B_2$.)

Orthogonal transformations preserve inner products, so in particular $\{Au_1,\ldots,Au_n\}$ is also an orthogonal representation and $$\langle c, u_i \rangle = \langle e_1, Au_i \rangle,$$ for each $i \in \{1,\ldots,n\}$. From this it should be easy to convince yourself that fixing an orthogonal representation and taking infimum over all unit vectors gives the same number as fixing a unit vector and taking infimum over all orthogonal representations.