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 be a graph on vertices. We consider the automorphism group of . That is, is a subgroup of the group of permutations on the set and for all , for all .
We consider a subgroup of . has a natural action on and we extend this action to the set of pairs . The set of orbits of is called the set of orbitals of on . Denote the set of orbitals by .
Notice that for each , we can represent it as a matrix over . Consider also the permutation representation of on the set , that is, we represent each as a permutation matrix. Now, we can show that the span of gives the set of matrices that commute with all elements in . That is,
Now, let us define a matrix to be the adjacency matrix of , that is, if is adjacent to and , otherwise. Observe that for all , by definition of a graph automorphism. Hence, is a linear combination of the orbitals. Since the orbitals partition the set and is a -matrix, then , for some set .
On the other hand, consider any subset . Let be the characteristic vector of . Then the set is independent if and only if .
Suppose is indeed independent and . We derive some necessary conditions for and . First, we consider the following matrix,
It is not difficult to observe that commutes with all and hence is a linear combination of the orbitals. Also, since and is positive semidefinite for all ,
Consider the all-ones matrix . Then on one hand,
On the other hand,
In addition, we consider the identity matrix . Again, by the same argument, , for some set (note that ). Then,
In summary, if is the characteristic vector of an independent set of size , then
Hence, `conversely’, if we attempt to maximise subject to the latter two conditions and obtain a value, say , then gives an upper bound to the size of any independent set of . Furthermore, if we impose an additional condition that for all , then we obtain a tigher bound .
In fact, is also known as the Lovász theta number (curiously, is independent of the choice of the group ) and Schrijver showed that gives the Delsartes bound for a set of graphs resulting from the Hamming scheme.