The hypergraph removal process
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_ | 1866913970527404032 |
|---|---|
| author | Joos, Felix Kühn, Marcus |
| author_facet | Joos, Felix Kühn, Marcus |
| contents | Let $k\geq 2$ and fix a $k$-uniform hypergraph $\mathcal{F}$. Consider the random process that, starting from a $k$-uniform hypergraph $\mathcal{H}$ on $n$ vertices, repeatedly deletes the edges of a copy of $\mathcal{F}$ chosen uniformly at random and terminates when no copies of $\mathcal{F}$ remain. Let $R(\mathcal{H},\mathcal{F})$ denote the number of edges that are left after termination. We show that $R(\mathcal{H},\mathcal{F})=n^{k-1/ρ\pm o(1)}$, where $ρ:=(\lvert E(\mathcal{F})\rvert-1)/(\lvert V(\mathcal{F})\rvert -k)$, holds with high probability provided that $\mathcal{F}$ is strictly $k$-balanced and $\mathcal{H}$ is sufficiently dense with pseudorandom properties. Since we may in particular choose $\mathcal{F}$ and $\mathcal{H}$ to be complete graphs, this confirms the major folklore conjecture in the area in a very strong form. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_15039 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The hypergraph removal process Joos, Felix Kühn, Marcus Combinatorics Probability Let $k\geq 2$ and fix a $k$-uniform hypergraph $\mathcal{F}$. Consider the random process that, starting from a $k$-uniform hypergraph $\mathcal{H}$ on $n$ vertices, repeatedly deletes the edges of a copy of $\mathcal{F}$ chosen uniformly at random and terminates when no copies of $\mathcal{F}$ remain. Let $R(\mathcal{H},\mathcal{F})$ denote the number of edges that are left after termination. We show that $R(\mathcal{H},\mathcal{F})=n^{k-1/ρ\pm o(1)}$, where $ρ:=(\lvert E(\mathcal{F})\rvert-1)/(\lvert V(\mathcal{F})\rvert -k)$, holds with high probability provided that $\mathcal{F}$ is strictly $k$-balanced and $\mathcal{H}$ is sufficiently dense with pseudorandom properties. Since we may in particular choose $\mathcal{F}$ and $\mathcal{H}$ to be complete graphs, this confirms the major folklore conjecture in the area in a very strong form. |
| title | The hypergraph removal process |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2412.15039 |