Short proof of the hypergraph container theorem
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916388511154176 |
|---|---|
| author | Nenadov, Rajko Pham, Huy Tuan |
| author_facet | Nenadov, Rajko Pham, Huy Tuan |
| contents | We present a short and simple proof of the celebrated hypergraph container theorem of Balogh--Morris--Samotij and Saxton--Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent set and constructing a hypergraph of lower uniformity which preserves independent sets and inherits edge distribution. The original algorithms for constructing containers also remove in each step vertices of high degree which are not in the independent set. Our modified algorithm postpones this until the end, which surprisingly results in a significantly simplified analysis. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_08514 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Short proof of the hypergraph container theorem Nenadov, Rajko Pham, Huy Tuan Combinatorics We present a short and simple proof of the celebrated hypergraph container theorem of Balogh--Morris--Samotij and Saxton--Thomason. On a high level, our argument utilises the idea of iteratively taking vertices of largest degree from an independent set and constructing a hypergraph of lower uniformity which preserves independent sets and inherits edge distribution. The original algorithms for constructing containers also remove in each step vertices of high degree which are not in the independent set. Our modified algorithm postpones this until the end, which surprisingly results in a significantly simplified analysis. |
| title | Short proof of the hypergraph container theorem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2408.08514 |