The Lovász theta function, and the variants of it given by Schrijver and Szegedy are upper bounds on the independence number of a graph. These functions play an important role in several optimization problems, such as the Cohn-Elkies bound for optimal sphere packing densities.
The Lovász theta function, and the variants of it given by Schrijver and Szegedy are upper bounds on the independence number of a graph. These functions play an important role in several optimization problems, such as the Cohn-Elkies bound for optimal sphere packing densities.
This thesis covers the properties of these functions. The main focus of this thesis is the multiplicity of Schrijver's variant. A construction for optimal solutions to the dual problem of this function for the disjunctive graph product is proposed, and its generality is studied.
It is shown that for abelian Cayley graphs, the Lovász theta function, and its variants reduce a linear program. Using properties of Fourier analysis an upper bound is given on the minimal gap between the largest and least eigenvalues of optimal solutions to the dual of Schrijver's variant. This, along with numerical results, suggests that the proposed construction is more likely to hold when abelian Cayley graphs are sparse.
