On the diameter of random uniform hypergraphs in dense regime

Abstract

For a fixed natural number $t\ge 2$, we consider $t$-uniform random hypergraphs $\mathcal{H}(n,t,p)$ on $n$ vertices $[n]=\{1,\dots ,n\}$, where each $t$-subset of $[n]$ is included as a hyperedge with probability $p$ and independently. We show that the diameter of $\mathcal{H}(n,t,p)$ is concentrated only at two points in the dense regime. More precisely, suppose $diam(\mathcal{H})$ denotes the diameter of a hypergraph $\mathcal{H}$ on $n$ vertices. We show that, for fixed $t,c,d$ constants, if $n$ and $p$ (depends on $t,c,d,n$) satisfy $$ \frac{ (t-1)^ {d} N^{d} p^{d}} {n}= \log \left( \frac{n^2}{c} \right), \mbox{ where } N={n-1\choose t-1}, $$ $c$ is a positive constant and $d\ge 2$ is a natural number, then $$\underset{n\to \infty }{\lim }\mathbb{P}\left(diam(\mathcal{H})=d\right)=e^{-\frac{c}{2}}\text{ and }\underset{n\to \infty }{\lim }\mathbb{P}\left(diam(\mathcal{H})=d+1\right)=1-e^{-\frac{c}{2}}.$$ In particular, the case where $t=2$ corresponds to the diameter of the Erdős-Rényi graph, as established by Bollobás in \cite[Theorem~6]{bollobas1981diameter}. Bollob\' as's result was proven using the moments method, which is challenging to apply in our context due to the complexity of the model. In this paper, we utilize the Stein-Chen method along with coupling techniques to prove our result. This approach can potentially be used to solve various problems, in particular diameter problems, in more complex networks.

arXiv comment31 pages