On the diameter of random uniform hypergraphs in dense regime

2025/12/04 by Adhikari, Kartick, Khatun, Asrafunnesa
Computer Science · Mathematics · #05C80 #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Random Matrices and Applications #Topological and Geometric Data Analysis

paper · doi:10.48550/arxiv.2512.04544

openalex publication_date 2025/12/04 · openalex created_date 2025/12/06 · openalex updated_date 2026/07/28

Abstract

For a fixed natural number t≥ 2, we consider t-uniform random hypergraphs \mathscrH (n,t,p) on n vertices [n]=\1,…, n\, where each t-subset of [n] is included as a hyperedge with probability p and independently. We show that the diameter of \mathscrH (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 ( (n²)/(c) ), where N=n-1\choose t-1, c is a positive constant and d≥2 is a natural number, then lim_{n → ∞} ℙ ( diam( H) = d ) = e^{- (c)/(2)} and lim_{n → ∞} ℙ ( diam(H) = d+1 ) = 1- e^{- (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.

Citations

• Spectrum and local weak convergence of sparse random uniform hypergraphs
• A simple model of global cascades on random hypergraphs
• Shotgun Assembly of Linial-Meshulam Model
• Evolution of Real-world Hypergraphs: Patterns and Models without Oracles
• Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
• Powers of Hamilton cycles in random graphs and tight Hamilton cycles in random hypergraphs
• Shotgun assembly of random regular graphs
• Closing gaps in problems related to Hamilton cycles in random graphs and hypergraphs
• Largest components in random hypergraphs
• Packing Hamilton Cycles in Random and Pseudo-Random Hypergraphs
• Stein's method and stochastic orderings
• Homological connectivity of random k-dimensional complexes
• The Structure and Function of Complex Networks
• Random graphs as models of networks
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations

Related

• A bound for the diameter of random hyperbolic graphs
• Diameter in ultra-small scale-free random graphs: Extended version
• Diameter of a new model of random hyperbolic surfaces
• The diameter of Inhomogeneous random graphs
• The diameter of KPKVB random graphs