Spectral bounds for the independence number and the chromatic number of an operator
Speaker:
Frank Vallentin, Tu Delft
Date and Time:
Monday, September 19, 2011 - 11:00am to 12:00pm
Abstract:
We extend the definition of the chromatic number and the independence number of finite graphs (and their adjacency matrices) to bounded, symmetric operators on Hilbert spaces. Furthermore, we extend results by Hoffman and Lovasz showing that the knowledge of the spectrum of the operator gives lower and upper bounds. This provides a theoretical framework in which many packing and coloring problems for finite and infinite graphs can be conveniently studied with the help of harmonic analysis and convex optimization. We apply it to infinite graphs on the unit sphere, to infinite graphs on Euclidean space, and to limits of graphs.