Hoffman bound for complexes

Hoffman bound for complexes

-
Yuval Filmus, Technion-Israel Institute of Technology, Haifa
Fine Hall 224

Many questions in extremal combinatorics can be framed as asking for the size of maximum independent sets in a graph. The prototypical example is the Erdős-Ko-Rado theorem and many of its generalizations. The Hoffman bound, closely related to the Lovász theta function, has been used to solve many of these questions. Other questions correspond to maximum independent sets in hypergraphs. Examples include the Erdős matching conjecture and s-wise intersecting families.

Bachoc, Gundert and Passuello generalized the theta function to complexes. We give a different generalization, and use it to solve Frankl's triangle problem, as well as give new proofs to several known results such as Mantel's theorem. Our bound is reminiscent of Garland's method, especially in its version due to Alev and Lau (arXiv:2001.02827, Theorem 1.5).

Joint work with Konstantin Golubev and Noam Lifshitz.