Konstantin Golubev High dimensional Hoffman bound and its applications to extremal combinatorics
The talk Highdimensional Hoffman bound and its applications to extremal combinatorics by Konstantin Golubev on the Moscow Conference on Combinatorics and Applications at MIPT. Annotation: The Hoffman bound is a spectral bound on the independence number of a graph. More precisely, it is an upper bound on the size of an independent set of a graph in terms of the smallest eigenvalue of its normalized adjacency operator. The bound has found numerous applications in extremal combinatorics, in particular, thanks to the work AlonDinurFriedgutSudakov. They exploit the following fact: if the Hoffman bound is sharp for a graph, it remains sharp for a tensor power of the graph. In joint work with Filmus and Lifshitz, we prove a generalization of the Hoffman bound for hypergraphs with a similar property: it remains sharp in a tensor power of a hypergraph. We apply the bound to several problems in extremal combinatorics: Frankls problem on extended triangles, Mantels Theorem, FranklTokushige T
|
|