Title:
The Theta Number of Simplicial Complexes
Abstract:
The celebrated Lovász theta number of a graph is an efficiently computable upper bound for the independence number of a graph, given by a semidefinite program. This talk presents a generalization of the theta number to simplicial complexes of arbitrary dimension, based on real simplicial cohomology theory, in particular higher dimensional Laplacians.
We will consider properties of the graph theta number such as the relationship to Hoffman’s ratio bound and to the chromatic number and study how they extend to higher dimensions and look at the value of the theta number for dense random simplicial complexes.
(Joint work with Christine Bachoc and Alberto Passuello)