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

Bachelor thesis (2023)

Authors

L.C. van der Waal Electrical Engineering, Mathematics and Computer Science

Contributors

D. de Laat Discrete Mathematics and Optimization - EEMCS (supervisor 1)
B. Janssens Analysis - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2023 Leon van der Waal
Optimization Graph theory Semidefinite programming
More Info
expand_more

Published Date

09-08-2023

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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.