Optimal spread for spanning subgraphs of Dirac hypergraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916375978573824 |
|---|---|
| author | Kelly, Tom Müyesser, Alp Pokrovskiy, Alexey |
| author_facet | Kelly, Tom Müyesser, Alp Pokrovskiy, Alexey |
| contents | Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to randomly embed $G$ into $H$ with good "spread". More precisely, for a wide class of $G$, we find a randomised embedding $f\colon G\hookrightarrow H$ with the following property: for every $s$, for any partial embedding $f'$ of $s$ vertices of $G$ into $H$, the probability that $f$ extends $f'$ is at most $O(1/n)^s$. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem. For example, setting $s=n$, we obtain an asymptotically tight lower bound on the number of embeddings of $G$ into $H$. This recovers and extends recent results of Glock, Gould, Joos, Kühn, and Osthus and of Montgomery and Pavez-Signé regarding enumerating Hamilton cycles in Dirac hypergraphs. Moreover, using the recent developments surrounding the Kahn--Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning $G$ still embeds into $H$ after a random sparsification of its edge set. This allows us to recover a recent result of Kang, Kelly, Kühn, Osthus, and Pfenninger and of Pham, Sah, Sawhney, and Simkin for perfect matchings, and obtain novel results for Hamilton cycles and factors in Dirac hypergraphs. Notably, our randomised embedding algorithm is self-contained and does not require Szemerédi's regularity lemma or iterative absorption. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_08535 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Optimal spread for spanning subgraphs of Dirac hypergraphs Kelly, Tom Müyesser, Alp Pokrovskiy, Alexey Combinatorics 05D40, 05C80 Let $G$ and $H$ be hypergraphs on $n$ vertices, and suppose $H$ has large enough minimum degree to necessarily contain a copy of $G$ as a subgraph. We give a general method to randomly embed $G$ into $H$ with good "spread". More precisely, for a wide class of $G$, we find a randomised embedding $f\colon G\hookrightarrow H$ with the following property: for every $s$, for any partial embedding $f'$ of $s$ vertices of $G$ into $H$, the probability that $f$ extends $f'$ is at most $O(1/n)^s$. This is a common generalisation of several streams of research surrounding the classical Dirac-type problem. For example, setting $s=n$, we obtain an asymptotically tight lower bound on the number of embeddings of $G$ into $H$. This recovers and extends recent results of Glock, Gould, Joos, Kühn, and Osthus and of Montgomery and Pavez-Signé regarding enumerating Hamilton cycles in Dirac hypergraphs. Moreover, using the recent developments surrounding the Kahn--Kalai conjecture, this result implies that many Dirac-type results hold robustly, meaning $G$ still embeds into $H$ after a random sparsification of its edge set. This allows us to recover a recent result of Kang, Kelly, Kühn, Osthus, and Pfenninger and of Pham, Sah, Sawhney, and Simkin for perfect matchings, and obtain novel results for Hamilton cycles and factors in Dirac hypergraphs. Notably, our randomised embedding algorithm is self-contained and does not require Szemerédi's regularity lemma or iterative absorption. |
| title | Optimal spread for spanning subgraphs of Dirac hypergraphs |
| topic | Combinatorics 05D40, 05C80 |
| url | https://arxiv.org/abs/2308.08535 |