Loose paths in random ordered hypergraphs
Andrzej Dudek, Alan Frieze, Wesley Pegden · 2025
Read Loose paths in random ordered hypergraphs by Andrzej Dudek, Alan Frieze, Wesley Pegden (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-2504-12196.txt.
Introduction
Andrzej Dudek, Alan Frieze, and Wesley Pegden work in pure mathematics in a 2025 paper. They study paths inside random hypergraphs, which are networks where each link can join many points at once.
They study a loose kind of path, where each step shares exactly its end point with the next step, and the points follow a fixed order. The question is how long the longest such path tends to be when the network is built at random. The authors prove fairly tight bounds on that length, bounds that hold with high probability. Results of this kind help map the hidden structure of random networks, a theme with echoes in coding and network design.
Catalog record
| CREATOR | Andrzej Dudek, Alan Frieze, Wesley Pegden |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 39 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-12196
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Loose paths in random ordered hypergraphs Thanks: The first author was supported in part by a grant from the Simons Foundation MPS-TSM-00007551. Thanks: The second author was supported in part by NSF grant DMS-2341774 Thanks: The third author was supported in part by NSF grant DMS-2054503 Andrzej Dudek, Alan Frieze, Wesley Pegden Abstract . We consider the length of ordered loose paths in the random r r -uniform hypergraph H = H ( r ) ( n , p ) H=H^{(r)}(n,p) . A ordered loose path is a sequence of edges E 1 , E 2 , … , E ℓ E_{1},E_{2},\ldots,E_{\ell} where max { j ∈ E i } = min { j ∈ E i + 1 } \max\left\{j\in E_{i}\right\}=\min\left\{j\in E_{i+1}\right\} for 1 ≤ i < ℓ 1\leq i<\ell . We establish fairly tight bounds on the length of the longest ordered loose path in H H that hold with high probability. 1. Introduction. There has been considerable work on the maximum length of paths in random graphs and hypergraphs, particularly in the graph case; see the survey by Frieze [ 2 ] for a summary what is known on the subject. Albert and Frieze [ 1 ] considered the maximum length of a path in an orientation of G_{n,p} where the edge \left\{i,j\right\},i<j was always oriented from i to j . In this paper we consider a generalization of this problem to r -uniform hypergraphs, where r\geq 2 is a fixed constant throughout. Let H=H^{(r)}(n,p) be the random r -uniform hypergraph on the set of vertices [n] such that each r -tuple in \binom{[n]}{r} is included as an edge with probability p . Let E_{p} denote its set of edges. Define an ordered loose path of length \ell in H as an increasing subsequence of vertices v_{1},v_{2},\dots,v_{\ell(r-1)+1}\in[n] such that \{v_{1}<\dots<v_{r}\},\{v_{r}<\dots<v_{2r-1}\},\dots,\{v_{(\ell-1)(r-1)+1}<\dots<v_{\ell(r-1)+1}\} are the edges of H (so that every pair of consecutive edges intersects in a single vertex). Let \ell_{\max} be the maximal length of an ordered loose path in H . In the following, we discuss the likely value of \ell_{\max} for varying values of p . Theorem 1.1 . Let r\geq 2 and \Omega(1)=p\leq 1-o(1) . Then, a.a.s. \frac{(1+o(1))n}{r-p-r(1-p)^{r}+(pr+1)(1-p)^{r}p^{-2}}\leq\ell_{\max}\leq(1+o(1))n\left(\frac{1}{r}+\frac{1}{r(r-2+p^{-1})}\right). Corollary 1.2 . Let 0<p<1 be a constant. Then, for every \varepsilon>0 there is an r_{0}=r_{0}(p,\varepsilon)\in\mathbb{N} such that for each r\geq r_{0} , we have a.a.s. \left(\frac{1}{r}-\varepsilon\right)n\leq\ell_{\max}\leq\left(\frac{1}{r}+\varepsilon\right)n. Corollary 1.3 . Let r\geq 2 and p=1-o(1) . Then, we have a.a.s. \ell_{\max}=\frac{(1+o(1))n}{r-1}. In fact, the upper bound in these corollaries is trivial (and no upper bound from Theorem 1.1 is needed), since always the length of an ordered loose path is at most \frac{n}{r-1}=n\left(\frac{1}{r}+\frac{1}{r(r-1)}\right) . However, notice that the second term of the upper bound in Theorem 1.1 is always smaller than the trivial one, since \frac{1}{r(r-2+p^{-1})}<\frac{1}{r(r-1)} when p<1 . Theorem 1.4 . Let r\geq 2 and \sqrt{\log n}/n^{(r-1)/4}\ll p=o(1) or \Omega((\log n)^{r-1}/n^{r-1})=p\ll 1/n^{(r-1)/2} . Then, a.a.s. \ell_{\max}=\Theta(np^{1/(r-1)}). (We write A_{n}\ll B_{n} (resp. B_{n}\gg A_{n} ) if A_{n}/B_{n}\to 0 as n\to\infty .) The next theorem fills the gap for the missing range of p from Theorem 1.4 . Unfortunately, this statement (likely the lower bound) is not optimal. Theorem 1.5 . Let r\geq 2 and \Omega(1/n^{(r-1)/2})=p=O(\sqrt{\log n}/n^{(r-1)/4}) . Then, a.a.s. \Omega(np^{1/(r-1)}/(\log n)^{1/(r-1)})=\ell_{\max}=O(np^{1/(r-1)}). The remaining (optimal) theorems describe results for the sparse regime. Theorem 1.6 . Let r\geq 3 and \omega=\omega(n) be such that 1\ll\omega\ll\log n and \frac{1}{n^{r-1+1/\omega}}\leq p=O((\log n)^{r-1}/n^{r-1}). Then, there exists 1\ll\ell_{0}=O(\log n) such that \left(\frac{n}{\ell_{0}}\right)^{r-1+1/\ell_{0}}p=1 and then a.a.s. \ell_{\max}=\Theta(\ell_{0}) . Theorem 1.7 . Let r\geq 3 and \ell\geq 2 be an integer. If 1/n^{r-1+1/\ell}\ll p\ll 1/n^{r-1+1/(\ell+1)} , then a.a.s. \ell_{\max}=\ell . Furthermore, let c>0 be a real number and p=c/n^{r-1+1/\ell} . Let X count the number of ordered paths of length \ell . Then, X converges in distribution to Po(\lambda) , where \lambda=c^{\ell}/(\ell(r-1)+1)! . Observe that if in Theorem 1.6 we allow \omega=\Theta(1) , then the lower bound on p is considered in Theorem 1.7 . Also if \omega=\Omega(\log n) , then p\geq\frac{1}{n^{r-1+1/\Omega(\log n)}}=\frac{1}{n^{r-1}}\frac{1}{n^{1/\Omega(\log n)}}=\Omega\left(\frac{1}{n^{r-1}}\right), which is contained in the range of p in Theorem 1.6 . 1.1. Outline of the paper Lemma 2.1 of Section 2 deals with the stochastic properties of edge length. This is followed by a technical lemma and the statement of a concentration inequality. We then divide the proof as shown in Table 1 . We have not managed to deal with small p , i.e., p=o((\log n)^{r-1}/n^{r-1}) . Section Bound Range of p 3 Lower \sqrt{\log n}/n^{(r-1)/4}\ll p\leq 1-o(1) 4 Lower \Omega(1/n^{(r-1)/2})=p=O(\sqrt{\log n}/n^{(r-1)/4}) 5 Lower \Omega((\log n)^{r-1}/n^{r-1})=p\ll 1/n^{(r-1)/2} 6 Upper p=\Omega((\log n)^{r-1}/n^{r-1}) 7 Lower/Upper \frac{1}{n^{r-1+1/\omega}}\leq p\leq O((\log n)^{r-1}/n^{r-1})\text{ or }1\ll\omega\ll\log n 8 Lower/Upper 1/(n^{r-1+1/\ell})\ll p\ll 1/(n^{r-1+1/(\ell+1)})\text{ where }\ell=O(1) Table 1. The structure of the proofs. 2. Preliminaries To bound the length of the longest ordered loose path from below, it is natural to consider a greedy algorithm, which extends an ordered loose path from its last vertex i by a hyperedge whose least vertex is i and whose “length” j-i , where j is its last vertex, is as small as possible. We will use the following lemma (about random hypergraphs of edges with common left endpoints) when considering the properties of such a greedy extension algorithm. Lemma 2.1 . Let H be a random r -hypergraph on the vertex set \mathbb{Z}^{+} such that each edge \{1<i_{2}<\dots<i_{r-1}<i_{r}\} appears with probability p . Let X_{i} (for i\geq 0 ) be a random variable, which equals r+i-1 if (I) \{1<i_{2}<\dots<i_{r-1}<i_{r}=r+i\} is present in H and (II) no edge of the form \{1<j_{2}<\dots<j_{r-1}<j_{r}\leq r+i-1\} is present in H , and is 0 otherwise. Define X=\sum_{i=0}^{\infty}X_{i} . Then: (i) The expected value equals \mbox{{\bf E}}X=\sum_{i=0}^{\infty}(r+i-1)(1-p)^{\binom{r-2+i}{r-1}}\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right). (ii) The expected value satisfies r-p-r(1-p)^{r}\leq\mbox{{\bf E}}X\leq r-p-r(1-p)^{r}+(pr+1)(1-p)^{r}p^{-2} and, in particular, for p=\Omega(1) , which is independent from r , \mbox{{\bf E}}X=r-p+o_{r}(1), where o_{r}(1) approaches zero as r tends to infinity. (iii) For p=o(1) , \mbox{{\bf E}}X=\Theta(1/p^{1/(r-1)}). Proof. We divide the proof into three parts. Part ( i ): For i=0 , clearly, \mbox{{\bf E}}X_{0}=(r-1)q_{0}p_{0} , where q_{0}=1 and p_{0}=p . Now consider i=1 . Here the edge \{1,\dots,r\} is not present (this happens with probability q_{1}=1-p_{0}=1-p ) and an edge e=\{1<i_{2}<\dots<i_{r-1}<r+1\} is present. Since we have exactly \binom{r-1}{r-2} choices for vertices i_{2}<\dots<i_{r-1} , the latter occurs with probability p_{1}=1-\left(1-p\right)^{\binom{r-1}{r-2}} . Thus, \mbox{{\bf E}}X_{1}=rq_{1}p_{1} . Assume in general that q_{i} is the probability of the event that no edge \{1<i_{2}<\dots<i_{r-1}<r+j\} for 0\leq j\leq i-1 is present. Moreover, let p_{i} be the probability of the event that there is an edge of the form \{1<i_{2}<\dots<i_{r-1}<r+i\} . Observe that q_{i}=q_{i-1}(1-p_{i-1})\quad\text{ and }\quad p_{i}=1-\left(1-p\right)^{\binom{r-2+i}{r-2}}. Thus, q_{i}=\prod_{j=0}^{i-1}(1-p_{j})=\prod_{j=0}^{i-1}\left(1-p\right)^{\binom{r-2+j}{r-2}}=(1-p)^{\sum_{j=0}^{i-1}\binom{r-2+j}{r-2}}=(1-p)^{\binom{r-2+i}{r-1}} and \mbox{{\bf E}}X_{i}=(r-1+i)(1-p)^{\binom{r-2+i}{r-1}}\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right). Consequently, \mbox{{\bf E}}X=\sum_{i=0}^{\infty}\mbox{{\bf E}}X_{i}=\sum_{i=0}^{\infty}(r-1+i)(1-p)^{\binom{r-2+i}{r-1}}\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right). Part ( ii ): We split the sum in the expression for \mbox{{\bf E}}X into two terms: \mbox{{\bf E}}X_{0}+\mbox{{\bf E}}X_{1} and \sum_{i=2}^{\infty}\mbox{{\bf E}}X_{i} . Observe that \mbox{{\bf E}}X_{0}+\mbox{{\bf E}}X_{1}=(r-1)p+r(1-p)\left(1-(1-p)^{r-1}\right)=r-p-r(1-p)^{r} and \sum_{i=2}^{\infty}\mbox{{\bf E}}X_{i}\leq\sum_{i=2}^{\infty}(r-1+i)(1-p)^{r-2+i}=(pr+1)(1-p)^{r}p^{-2}. Since \mbox{{\bf E}}X_{0}+\mbox{{\bf E}}X_{1}\leq\mbox{{\bf E}}X=\mbox{{\bf E}}X_{0}+\mbox{{\bf E}}X_{1}+\sum_{i=2}^{\infty}\mbox{{\bf E}}X_{i} , we obtain r-p-r(1-p)^{r}\leq\mbox{{\bf E}}X\leq r-p-r(1-p)^{r}+(pr+1)(1-p)^{r}p^{-2}. Finally notice that both \lim_{r\to\infty}r(1-p)^{r}=0 and \lim_{r\to\infty}(pr+1)(1-p)^{r}p^{-2}=0 for any p=\Omega(1) which is independent from r . This yields \mbox{{\bf E}}X=r-p+o_{r}(1) . Part ( iii ): For r=2 observe that \mbox{{\bf E}}X=\sum_{i=0}^{\infty}(1+i)(1-p)^{i}p=p\sum_{i=0}^{\infty}(1+i)(1-p)^{i}=p\cdot\frac{1}{p^{2}}=1/p, as required. Therefore, we may assume that r\geq 3 . We split the sum into two terms: S_{1}=\sum_{0\leq i\leq(r-1)/p^{1/(r-1)}}(r-1+i)(1-p)^{\binom{r-2+i}{r-1}}\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right), and S_{2}=\sum_{(r-1)/p^{1/(r-1)}<i}(r-1+i)(1-p)^{\binom{r-2+i}{r-1}}\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right). Observe that \displaystyle S_{1} \displaystyle\leq\sum_{0\leq i\leq(r-1)/p^{1/(r-1)}}(r-1+i)\left(1-\left(1-p\right)^{\binom{r-2+i}{r-2}}\right) \displaystyle\leq\sum_{0\leq i\leq(r-1)/p^{1/(r-1)}}(r-1+i)\left(1-\left(1-p{\binom{r-2+i}{r-2}}\right)\right) \displaystyle=p\sum_{0\leq i\leq(r-1)/p^{1/(r-1)}}(r-1+i)\binom{r-2+i}{r-2}