Konstantin Golubev - “High-dimensional Hoffman bound and its applications to extremal combinatorics“

The talk “High-dimensional 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 Alon-Dinur-Friedgut-Sudakov. 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: Frankl’s problem on extended triangles, Mantel’s Theorem, Frankl-Tokushige T