Berge Hamilton cycles in a random sparsification of dense hypergraphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866908906338385920 |
|---|---|
| author | Im, Seonghyuk Kim, Minseo |
| author_facet | Im, Seonghyuk Kim, Minseo |
| contents | In the standard random graph process, edges are added to an initially empty graph one by one uniformly at random. A classic result by Ajtai, Komlós, and Szemerédi, and independently by Bollobás, states that in the standard random graph process, with high probability, the graph becomes Hamiltonian exactly when its minimum degree becomes $2$; this is known as a \emph{hitting time} result. Johansson extended this result by showing the following: For a graph $G$ with $δ(G) \geq (1/2+\varepsilon)n$, in the random graph process constrained to the host graph $G$, the hitting times for minimum degree $2$ and Hamiltonicity still coincide with high probability.
In this paper, we extend Johansson's result to Berge Hamilton cycles in hypergraphs. We prove that if an $r$-uniform hypergraph $H$ satisfies either $δ_1(H) \geq (\frac{1}{2^{r-1}} + \varepsilon)\binom{n-1}{r-1}$ or $δ_2(H) \geq \varepsilon n^{r-2}$, then in the random process generated by the edges of $H$, the time at which the hypergraph reaches minimum degree $2$ coincides with the time at which it contains a Berge Hamilton cycle with high probability. In addition, we prove an analogous result for weak Berge Hamilton cycles. This generalizes the work of Bal, Berkowitz, Devlin, and Schacht, who established the result for the case where $H$ is a complete $r$-uniform hypergraph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_06675 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Berge Hamilton cycles in a random sparsification of dense hypergraphs Im, Seonghyuk Kim, Minseo Combinatorics In the standard random graph process, edges are added to an initially empty graph one by one uniformly at random. A classic result by Ajtai, Komlós, and Szemerédi, and independently by Bollobás, states that in the standard random graph process, with high probability, the graph becomes Hamiltonian exactly when its minimum degree becomes $2$; this is known as a \emph{hitting time} result. Johansson extended this result by showing the following: For a graph $G$ with $δ(G) \geq (1/2+\varepsilon)n$, in the random graph process constrained to the host graph $G$, the hitting times for minimum degree $2$ and Hamiltonicity still coincide with high probability. In this paper, we extend Johansson's result to Berge Hamilton cycles in hypergraphs. We prove that if an $r$-uniform hypergraph $H$ satisfies either $δ_1(H) \geq (\frac{1}{2^{r-1}} + \varepsilon)\binom{n-1}{r-1}$ or $δ_2(H) \geq \varepsilon n^{r-2}$, then in the random process generated by the edges of $H$, the time at which the hypergraph reaches minimum degree $2$ coincides with the time at which it contains a Berge Hamilton cycle with high probability. In addition, we prove an analogous result for weak Berge Hamilton cycles. This generalizes the work of Bal, Berkowitz, Devlin, and Schacht, who established the result for the case where $H$ is a complete $r$-uniform hypergraph. |
| title | Berge Hamilton cycles in a random sparsification of dense hypergraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.06675 |