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.

31 pages