Towards an Optimal Hypergraph Container Lemma

Authors:
Open Access
Publisher website
Google Scholar
Abstract
The hypergraph container lemma is a powerful tool in probabilistic combinatorics that has found many applications since it was first proved a decade ago. Roughly speaking, it asserts that the family of independent sets of every uniform hypergraph can be covered by a small number of almost-independent sets, called containers. In this article, we formulate and prove two new versions of the lemma that display the following three attractive features. First, they both admit short proofs that have surprising connections to other well-studied topics in probabilistic combinatorics. Second, they use alternative notions of almost-independence in order to describe the containers. Third, they yield improved dependence of the number of containers on the uniformity of the hypergraph, hitting a natural barrier for second-moment-type approaches.
Funding Information
  • Instituto Nacional de Matematica Pura e Aplicada

This publication has 24 references indexed in Scilit: