Exact threshold and limiting distribution for non-linear Hamilton cycles
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916553023291392 |
|---|---|
| author | Chin, Byron |
| author_facet | Chin, Byron |
| contents | For positive integers $r > \ell \geq 1$, an $\ell$-cycle in an $r$-uniform hypergraph is a cycle where each edge consists of $r$ vertices and each pair of consecutive edges intersect in $\ell$ vertices. For $\ell \geq 2$, we determine the limiting distribution of the number of Hamilton $\ell$-cycles in an Erdős--Rényi random hypergraph. The behavior is distinguished in two cases:
-When $\ell \geq 3$, the number of cycles concentrates when the expectation diverges and converges to a Poisson distribution when the expectation is constant.
-When $\ell = 2$, the normalized number of cycles converges to a lognormal distribution when the expectation diverges and converges to a lognormal mixture of Poisson distributions when the expectation is constant.
As a result we pin down the exact threshold for the appearance of non-linear Hamilton cycles in random hypergraphs, confirming a conjecture of Narayanan and Schacht. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_13452 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact threshold and limiting distribution for non-linear Hamilton cycles Chin, Byron Combinatorics Probability For positive integers $r > \ell \geq 1$, an $\ell$-cycle in an $r$-uniform hypergraph is a cycle where each edge consists of $r$ vertices and each pair of consecutive edges intersect in $\ell$ vertices. For $\ell \geq 2$, we determine the limiting distribution of the number of Hamilton $\ell$-cycles in an Erdős--Rényi random hypergraph. The behavior is distinguished in two cases: -When $\ell \geq 3$, the number of cycles concentrates when the expectation diverges and converges to a Poisson distribution when the expectation is constant. -When $\ell = 2$, the normalized number of cycles converges to a lognormal distribution when the expectation diverges and converges to a lognormal mixture of Poisson distributions when the expectation is constant. As a result we pin down the exact threshold for the appearance of non-linear Hamilton cycles in random hypergraphs, confirming a conjecture of Narayanan and Schacht. |
| title | Exact threshold and limiting distribution for non-linear Hamilton cycles |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2411.13452 |