Lovasz theta number

Posted: May 5, 2011 in Lectures, Representation Theory

It has been quite some time since I’ve blogged. Perhaps it is appropriate to post one entry on the last lesson in class. This is also my attempt to use LaTeX2WP, which `is a program that converts a LaTeX file into something that is ready to be cut and pasted into WordPress’.

Let ${\Gamma=(\Omega,E)}$ be a graph on ${|\Omega|=n}$ vertices. We consider the automorphism group ${Aut(\Gamma)}$ of ${\Gamma}$ . That is, ${Aut(\Gamma)}$ is a subgroup of the group of permutations on the set ${\Omega}$ and for all ${g\in Aut(\Gamma)}$ , ${(gx,gy)\in E}$ for all ${(x,y)\in E}$ .

We consider a subgroup ${G}$ of ${Aut(\Gamma)}$ . ${G}$ has a natural action on ${\Omega}$ and we extend this action to the set of pairs ${\Omega\times\Omega}$ . The set of orbits of ${\Omega\times\Omega}$ is called the set of orbitals of ${G}$ on ${\Omega}$ . Denote the set of orbitals by ${\mathcal O}$ .

Notice that for each ${O\in\mathcal O}$ , we can represent it as a ${n\times n}$ matrix over ${\{ 0,1 \}}$ . Consider also the permutation representation of ${G}$ on the set ${\Omega}$ , that is, we represent each ${g\in G}$ as a ${n\times n}$ permutation matrix. Now, we can show that the span of ${\{O:O\in\mathcal O\}}$ gives the set of matrices that commute with all elements in ${G}$ . That is,

$\displaystyle gMg^{-1}=M \mbox{ for all }g\in G \Rightarrow M=\sum_{O\in\mathcal O}a_O O \mbox{, for some }a_O\in {\mathbb C}.$

Now, let us define a ${n\times n}$ matrix ${A}$ to be the adjacency matrix of ${\Gamma}$ , that is, ${(A)_{uv}=1}$ if ${u}$ is adjacent to ${v}$ and ${0}$ , otherwise. Observe that for all ${g\in G}$ , ${gAg^{-1}=gAg^T=A}$ by definition of a graph automorphism. Hence, ${A}$ is a linear combination of the orbitals. Since the orbitals partition the set ${\Omega\times\Omega}$ and ${A}$ is a ${\{ 0,1 \}}$ -matrix, then ${A=\sum_{O\in \mathcal A} O}$ , for some set ${\mathcal A}$ .

On the other hand, consider any subset ${S\subset\Omega}$ . Let ${c}$ be the ${n\times 1}$ characteristic vector of ${S}$ . Then the set ${S}$ is independent if and only if ${\langle cc^T,A\rangle=0}$ .

Suppose ${S}$ is indeed independent and ${|S|=\alpha}$ . We derive some necessary conditions for ${c}$ and ${\alpha}$ . First, we consider the following ${n\times n}$ matrix,

$\displaystyle C:=\frac 1{\alpha|G|}\sum_{g\in G} (gc)(gc)^T.$

It is not difficult to observe that ${C}$ commutes with all ${g\in G}$ and hence ${C}$ is a linear combination of the orbitals. Also, since ${\langle C,A\rangle =0}$ and ${(gc)(gc)^T}$ is positive semidefinite for all ${g\in G}$ ,

$\displaystyle C=\sum_{O\notin \mathcal A} x_O O \succeq 0.$

Consider the all-ones matrix ${J=\sum_{O\in\mathcal O}O}$ . Then on one hand,

$\displaystyle \langle C,\sum_{O\in\mathcal O}O\rangle=\langle \sum_{O\notin \mathcal A} x_O O,\sum_{O\in\mathcal O}O\rangle=\sum_{O\notin \mathcal A} x_O\langle O,O\rangle.$

On the other hand,

$\displaystyle \langle\frac 1{\alpha|G|}\sum_{g\in G} (gc)(gc)^T,J\rangle=\frac 1{\alpha|G|}\sum_{g\in G}\langle gc(gc)^T,J\rangle=\frac 1{\alpha|G|}\sum_{g\in G}c^TJc=\frac{\alpha^2}\alpha=\alpha.$

In addition, we consider the identity matrix ${I}$ . Again, by the same argument, ${I=\sum_{O\in \mathcal D} O}$ , for some set ${\mathcal D}$ (note that ${\mathcal A\cap\mathcal D=\emptyset}$ ). Then,

$\displaystyle \langle C,\sum_{O\in\mathcal D}O\rangle=\cdots=\sum_{O\in\mathcal D} x_O\langle O,O\rangle.$

Also,

$\displaystyle \langle\frac 1{\alpha|G|}\sum_{g\in G} (gc)(gc)^T,I\rangle=\frac 1{\alpha|G|}\sum_{g\in G}\mbox{Trace}(cc^T)=1.$

In summary, if ${c}$ is the characteristic vector of an independent set of size ${\alpha}$ , then

$\displaystyle \alpha=1+\sum_{O\notin \mathcal A\cup\mathcal D} \langle O,O\rangle x_O,$

where

$\displaystyle C=\sum_{O\notin \mathcal A} x_O O \succeq 0,$

and

$\displaystyle \sum_{O\in\mathcal D} x_O\langle O,O\rangle=1.$

Hence, `conversely’, if we attempt to maximise ${\alpha}$ subject to the latter two conditions and obtain a value, say ${\theta(\Gamma)}$ , then ${\theta(\Gamma)}$ gives an upper bound to the size of any independent set of ${\Gamma}$ . Furthermore, if we impose an additional condition that ${x_O\ge 0}$ for all ${O\notin\mathcal A}$ , then we obtain a tigher bound ${\theta^\prime(\Gamma)}$ .

In fact, ${\theta(\Gamma)}$ is also known as the Lovász theta number (curiously, ${\theta(\Gamma)}$ is independent of the choice of the group ${G}$ ) and Schrijver showed that ${\theta^\prime(\Gamma)}$ gives the Delsartes bound for a set of graphs resulting from the Hamming scheme.

About these ads

a short fat boy and his chalkboard

Contact Information

Categories

Links

Archives

Lovasz theta number

Like this:

Leave a Reply Cancel reply

Follow “a short fat boy and his chalkboard”