Towards an optimal hypergraph container lemma
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916400806756352 |
|---|---|
| author | Campos, Marcelo Samotij, Wojciech |
| author_facet | Campos, Marcelo Samotij, Wojciech |
| contents | 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 and simple 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_06617 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Towards an optimal hypergraph container lemma Campos, Marcelo Samotij, Wojciech Combinatorics 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 and simple 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. |
| title | Towards an optimal hypergraph container lemma |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.06617 |