On the Dual of the Lovász Theta Prime Number for the Disjunctive Product of Graphs

On the Dual of the Lovász Theta Prime Number for the Disjunctive Product of Graphs

van der Waal, Leon (TU Delft Electrical Engineering, Mathematics and Computer Science)

de Laat, D. (mentor)
Janssens, B. (graduation committee)

Delft University of Technology

Applied Mathematics

2023-08-09

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.

Optimization
Graph theory
Semidefinite programming

http://resolver.tudelft.nl/uuid:883e3ba8-3a57-4757-8493-1a5a8cf1519f

Student theses

bachelor thesis

© 2023 Leon van der Waal