Independent sets and spectral method

Event time: 
Thursday, September 19, 2019 - 3:00pm
Konstantin Golubev
Speaker affiliation: 
ETH Zurich
Event description: 

Abstract: In 1970, Hoffman gave a spectral upper bound on the size of an independent set of a graph. Since then it found applications and generalizations in different fields. In particular, the original bound and its generalization to hypergraphs became a powerful tool in extreme combinatorics by providing a spectral proof to a number of problems, e.g., Erdos-Ko-Rado, Deza-Frankl, Mantel Theorems, and others. The usual approach is to show that an explicit family of objects is extreme by showing that its size achieves the Hoffman bound in the (hyper-)graph of constraints. It turns out that these examples of independent sets in graphs are also extreme for the question of sampling on graphs posed recently by Steinerberger. If time permits, I’ll also talk about the spectral approach to independent sets on the hyperbolic plane and its quotients.