The threshold for loose Hamilton cycles in random hypergraphs
Alan Frieze, Xavier Pérez-Giménez · 2025
Read The threshold for loose Hamilton cycles in random hypergraphs by Alan Frieze, Xavier Pérez-Giménez (2025) 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-2503-05121.txt.
Introduction
Alan Frieze and Xavier Pérez-Giménez pinned down a threshold in random hypergraph theory in 2025. A hypergraph links groups of points at once, and a loose Hamilton cycle is a ring that visits every point while consecutive hyperedges overlap in exactly one point. The question is how many random hyperedges a hypergraph needs before such a spanning ring almost certainly exists.
The authors show that once the number of hyperedges passes a precise edge, growing with the number of points and its logarithm. A loose Hamilton cycle appears with high chance, for every uniformity of three or more. The bound is asymptotically best possible: just below it, isolated points almost certainly remain, and a cycle visiting every point is then impossible. Threshold results of this kind are the backbone of random form theory.
Catalog record
| CREATOR | Alan Frieze, Xavier Pérez-Giménez |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 41 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-05121
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
The threshold for loose Hamilton cycles in random hypergraphs Alan Frieze, Xavier Pérez-Giménez Abstract We show that w.h.p. the random r r -uniform hypergraph H n , m H_{n,m} contains a loose Hamilton cycle, provided r ≥ 3 r\geq 3 and m ≥ ( 1 + ϵ ) n log n r m\geq\frac{(1+\epsilon)n\log n}{r} , where ϵ \epsilon is an arbitrary positive constant. This is asymptotically best possible, as if m ≤ ( 1 − ϵ ) n log n r m\leq\frac{(1-\epsilon)n\log n}{r} then w.h.p. H n , m H_{n,m} contains isolated vertices. 1 Introduction The thresholds for the existence of Hamilton cycles in the random graphs G_{n,m},G_{n,p} have been known for many years, see [ 1 ] , [ 3 ] and [ 15 ] . There have been many generalisations of these results over the years and the problem is well understood. It is natural to try to extend these results to hypergraphs. An r -uniform hypergraph is a pair H=(V,E) where E\subseteq\binom{V}{r} . Let H_{n,p} be the binomial random r -uniform hypergraph on n vertices with edge probability p . (The uniformity is r thoughout and so we drop r from some of the notation.) Let H_{n,m} be the random r -uniform hypergraph on n vertices with m randomly chosen E_{m} edges from \binom{V}{r} . We are also interested in oriented hypergraphs in which each edge has one distinguished vertex called its tail and r-1 heads . Let \vec{H}_{n,p} be the oriented counterpart of H_{n,p} in which each one of the r\binom{n}{r} possible oriented edges is picked independently with probability p . Note that if we take \vec{H}_{n,p} and ignore the orientations, then the outcome is distributed as H_{n,p^{\prime}} with p^{\prime}=1-(1-p)^{r} , so p^{\prime}\sim rp when p=o(1) . We say that an r -uniform sub-hypergraph C of H is a Hamilton cycle of type \ell , for some 1\leq\ell\leq r-1 , if there exists a cyclic ordering of the vertices V such that every edge consists of r consecutive vertices and for every pair of consecutive edges e_{i-1},e_{i} in C (in the natural ordering of the edges) we have |e_{i-1}\setminus e_{i}|=\ell . When \ell=r-1 we say that C is a loose Hamilton cycle. Frieze [ 10 ] , Dudek and Frieze [ 5 ] and Dudek, Frieze, Loh and Speiss [ 6 ] established the threshold for the existence of a loose Hamilton cycle in H_{n,m} up to a constant factor. (See also, Ferber [ 7 ] and Frankston, Kahn, Narayanan and Park [ 8 ] .) We will prove the following theorem: Theorem 1 . Let \varepsilon>0 be an arbitrary small positive constant. If r\geq 3 and (r-1)\mid n and m\geq\frac{(1+\varepsilon)n\log n}{r} then w.h.p. H_{n,m} contains a loose Hamilton cycle. If m\leq\frac{(1-\varepsilon)n\log n}{r} then w.h.p. H_{n,m} contains isolated vertices and so this is asymptotically best possible. (The constraint (r-1)\mid n is necessary for the existence of a loose Hamilton cycle. We should also remark that Narayanan and Schacht [ 16 ] obtained the precise threshold for type \ell cycles, except for the case of loose Hamilton cycles.) We need the following result of Altman, Greenhill, Isaev and Ramadurai [ 2 ] . They proved the following theorem: let H_{n,d} denote a random d -regular, r -uniform hypergraph on vertex set [n] . Theorem 2 . Suppose that r\mid dn and r-1\mid n . Then, \lim_{n\to\infty}\mathbb{P}(H_{n,d}\text{ contains a loose Hamilton cycle})=\begin{cases}1&d>\rho(r).\\ 0&d\leq\rho(r).\end{cases} Here \rho=\rho(r) is the unique real in (2,\infty) such that (\rho-1)(r-1)\left(\frac{\rho r-d-r}{\rho r-\rho}\right)^{(r-1)(\rho r-\rho-r)/r}=1. We also need (the proof of) the following theorem of Kahn [ 13 ] : Theorem 3 . Let \varepsilon>0 be an arbitrary positive constant. If r\mid n and m\geq\frac{(1+\varepsilon)n\log n}{r} then w.h.p. H_{n,m} contains a perfect matching. 2 Proof of Theorem 1 Let {\mathcal{K}}=\binom{[n]}{r} denote the edges of the complete r -uniform hypergraph with vertex set [n] . Let N=|{\mathcal{K}}|=\binom{n}{r} . Let \hat{H}_{n,d} be the random (multi)-hypergraph in which every vertex v picks a random set of d edges that contain v . Each edge is picked independently of other choices and with replacement, so in principle one vertex could pick the same edge twice or two different vertices may pick the same edge. However, neither of these situations will occur w.h.p for d=d^{*}=\varepsilon^{2}\log n , which is what we are interested in. We can think of \hat{H}_{n,d} as a hypergraph generalization of the d -out model of random graphs. For convenience, we may sometimes regard \hat{H}_{n,d} as oriented by making each vertex be the tail of all the edges that it picked. We will be concerned with H_{n,p} for p=(1+\varepsilon)p_{*} where p_{*}=\log n/\binom{n-1}{r-1} and \varepsilon>0 is a small constant. Theorem 4 . Let d^{*}=\varepsilon^{2}\log n , p=(1+\varepsilon)\log n/\binom{n-1}{r-1} and \rho\in\mathbb{N} constant. Then, there is a coupling in which H_{n,p} contains \rho independent copies {\widehat{\Gamma}}_{1},{\widehat{\Gamma}}_{2},\ldots,{\widehat{\Gamma}}_{\rho} of \hat{H}_{n,d^{*}} w.h.p. Proof. We will consider three types of edges: 1 , 2 and 3 . Edges of types 1 and 3 are oriented, i.e. they have a distinguished vertex called tail and r-1 heads. Edges of type 2 are not oriented. \vec{E}_{1},E_{2},\vec{E}_{3} will be auxiliary random hypergraphs on [n] with edges of types 1,2,3 , respectively, and built independently of each other. \vec{E}_{1} is built by picking each one of the r\binom{n}{r} possible oriented edges with probability p_{1}=1-\left(1-\frac{\varepsilon}{2}p_{*}\right)^{1/r}\sim\frac{\varepsilon}{2r}p_{*} independently from other choices. So \vec{E}_{1} is distributed as \vec{H}_{n,p_{1}} . E_{2} is distributed like H_{n,p_{2}} (unoriented) with p_{2}=(1+\varepsilon/2)p_{*} . Finally, \vec{E}_{3} is distributed as \vec{H}_{n,p_{3}} with (1-p_{3})^{r}=1-p_{2} , so p_{3}\sim p_{2}/r . Note that if E_{i} ( i\in\{1,3\} ) is obtained from \vec{E}_{1},\vec{E}_{3} by forgetting the orientation of the vertices, then it is distributed as H_{n,\tilde{p}_{i}} , where \tilde{p}_{i}=1-(1-p_{i})^{r}\sim rp_{i} (more precisely, \tilde{p}_{1}=\frac{\varepsilon}{2}p_{*} and \tilde{p}_{3}=p_{2}=(1+\varepsilon/2)p_{*} ). Therefore, there is no hope of embedding E_{1}\cup E_{2}\cup E_{3} inside of H_{n,p} since each one of E_{2} and E_{3} have almost the same number of edges as H_{n,p} , so the union contains almost twice the needed edges. So our approach will be to consider all edges of type 1 together with some of type 2 and some of type 3 in a way that we can build the desired coupling. We generate \vec{E}_{1} as the union of \rho independent copies \vec{E}^{(1)}_{1},\ldots,\vec{E}^{(\rho)}_{1} of \vec{H}_{n,p^{\prime}_{1}} with (1-p^{\prime}_{1})^{\rho}=1-p_{1} , so p^{\prime}_{1}\sim p_{1}/\rho=\frac{\varepsilon}{2r\rho}p_{*} . Given a vertex v in an oriented hypergraph, its out-edges are the edges that have v as a tail. Out-degrees and other related notions are defined the obvious way. We say v is good if its out-degree is at least d^{*} in every \vec{E}^{(1)}_{1},\ldots,\vec{E}^{(\rho)}_{1} . Otherwise we call vertex v bad . Lemma 5 . Let H_{1},H_{2},\ldots,H_{\rho} be independent copies of \vec{H}_{n,\alpha p_{*}} for some \alpha>0 . Let V_{\alpha} denote the set of vertices of degree less than d^{*} in at least one of the L_{i} . Then \mathbb{E}(|V_{\alpha}|)\leq n^{\theta_{\alpha}} where \theta_{\alpha}=\varepsilon^{2}(\log 1/\varepsilon^{2}+1+\log\alpha)-\alpha . Proof. Let p_{\alpha}=\alpha p_{*} . Then, \displaystyle E(|V_{\alpha}|) \displaystyle\leq n\rho\sum_{k=0}^{d^{*}}\binom{\binom{n-1}{r-1}}{k}p_{\alpha}^{k}(1-p_{\alpha})^{\binom{n-1}{r-1}-k} \displaystyle\leq 2n\rho\left(\frac{\binom{n-1}{r-1}p_{\alpha}e}{\varepsilon^{2}\log n}\right)^{\varepsilon^{2}\log n}\exp\left\{-\left(\binom{n-1}{r-1}-k\right)p_{\alpha}\right\} \displaystyle\leq 3n\rho\left(\frac{e\alpha}{\varepsilon^{2}}\right)^{\varepsilon^{2}\log n}n^{-\alpha} \displaystyle=O(n^{1+\theta_{\alpha}}). ∎ Putting \alpha=\varepsilon/(2r\rho) in Lemma 5 and using the Markov inequality, we see that w.h.p. all but at most a 1/n^{\varepsilon^{\prime}} fraction of the vertices are good, where \varepsilon^{\prime}=\varepsilon^{\prime}(\varepsilon,r,\rho)>0 . We call this event \mathcal{F}_{1} . Now we will consider a hypergraph that contains all edges of type