The hypergraph removal process
Felix Joos, Marcus Kühn · 2024
Read The hypergraph removal process by Felix Joos, Marcus Kühn (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-15039.txt.
Introduction
Felix Joos and Marcus Kühn study, in a 2024 math paper, a random process that chews through a hypergraph by deleting copies of a fixed pattern. A hypergraph links groups of points, not just pairs. The process starts from a dense, well-mixed hypergraph and keeps removing a randomly chosen copy of the pattern. It stops only when no copy is left. The question is how many edges survive.
The pair pin down that leftover count with high probability, giving a tight formula tied to the pattern's shape. Their proof needs the pattern to be strictly balanced and the starting hypergraph to be dense and random-like. Since complete graphs fit as a special case, the result confirms a long-standing folk conjecture in the field, and in a strong form.
Catalog record
| CREATOR | Felix Joos, Marcus Kühn |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 731 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-15039