Algebraic Graph Theory Seminar - Gabriel Coutinho

Title: Optimizing sums of eigenvalues

Abstract:

In its original proof, Hoffman's well known lower bound to the chromatic number is obtained after replacing several terms of a sum of eigenvalues by the smallest eigenvalue of the graph. This apparent waste is overshadowed by the fact that so many graphs meet the lower bound with equality, and that its optimized version is in fact equal to the ubiquitous Lovász theta number of the graph.

In this talk, we explore what happens if one decides to not replace all those eigenvalues by the smallest, but still insists in optimizing the bound. We will see that the resulting lower bound is better than the theta number, but no better than the fractional chromatic number. Connections to a variant of the theta number and to the quantum variant of the chromatic number will be made explicit.
This talk is based on joint work with M.K. de Carli Silva and R. Grandsire.