Subcritical Random Hypergraphs, High-Order Components, and Hypertrees
Authors:
- Oliver CooleyOCOliver Cooley
- Wenjie FangWFWenjie Fang
- Nicola Del GiudiceNGNicola Del Giudice
- Mihyun KangMKMihyun Kang
- 1 January 2020
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 34 (4) , 2033-2062
Abstract
One of the central topics in the theory of random graphs deals with the phase transition in the order of the largest components. In the binomial random graph $\mathcal{G}(n,p)$, the threshold for the appearance of the unique largest component (also known as the giant component) is $p_g = n^{-1}$. More precisely, when $p$ changes from $(1-\varepsilon)p_g$ (subcritical case) to $p_g$ and then to $(1+\varepsilon)p_g$ (supercritical case) for $\varepsilon>0$, with high probability the order of the largest component increases smoothly from $O(\varepsilon^{-2}\log(\varepsilon^3 n))$ to $\Theta(n^{2/3})$ and then to $(1 \pm o(1)) 2 \varepsilon n$. Furthermore, in the supercritical case, with high probability the largest components except the giant component are trees of order $O(\varepsilon^{-2}\log(\varepsilon^3 n))$, exhibiting a structural symmetry between the subcritical random graph and the graph obtained from the supercritical random graph by deleting its giant component. As a natural generalization of random graphs and connectedness, we consider the binomial random $k$-uniform hypergraph $\mathcal{H}^k(n,p)$ (where each $k$-tuple of vertices is present as a hyperedge with probability $p$ independently) and the following notion of high-order connectedness. Given an integer $1 \leq j \leq k-1$, two sets of $j$ vertices are called $j$-connected if there is a walk of hyperedges between them such that any two consecutive hyperedges intersect in at least $j$ vertices. A $j$-connected component is a maximal collection of pairwise $j$-connected $j$-tuples of vertices. Recently, the threshold for the appearance of the giant $j$-connected component in $\mathcal{H}^k(n,p)$ and its order were determined. In this article, we take a closer look at the subcritical random hypergraph. We determine the structure, order, and size of the largest $j$-connected components, with the help of a certain class of “hypertrees” and related objects. In our proofs, we combine various probabilistic and enumerative techniques, such as generating functions and couplings with branching processes. Our study will pave the way to establishing a symmetry between the subcritical random hypergraph and the hypergraph obtained from the supercritical random hypergraph by deleting its giant $j$-connected component.
Keywords
Funding Information
- Austrian Science Fund (W1230, P27290)
This publication has 25 references indexed in Scilit:
- Vanishing of cohomology groups of random simplicial complexesRandom Structures & Algorithms, 2019
- The size of the giant high‐order component in random hypergraphsRandom Structures & Algorithms, 2018
- Exploring hypergraphs with martingalesRandom Structures & Algorithms, 2016
- Inside the critical window for cohomology of random k -complexesRandom Structures & Algorithms, 2015
- Asymptotic normality of the size of the giant component in a random hypergraphRandom Structures & Algorithms, 2012
- The order of the giant component of random hypergraphsRandom Structures & Algorithms, 2009
- Homological connectivity of random k‐dimensional complexesRandom Structures & Algorithms, 2008
- The phase transition in inhomogeneous random graphsRandom Structures & Algorithms, 2007
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990
- Component structure in the evolution of random hypergraphsCombinatorica, 1985