2018/10/18 by Oliver Cooley, Wenjie Fang, Cooley, Oliver +5
Mathematics · Computer Science · #Stochastic processes and statistical mechanics #Topological and Geometric Data Analysis #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1810.08107
In the binomial random graph G(n,p), when p changes from (1-ε)/n (subcritical case) to 1/n and then to (1+ε)/n (supercritical case) for ε>0, with high probability the order of the largest component increases smoothly from O(ε-2log(ε3 n)) to Θ(n2/3) and then to (1 ± o(1)) 2 ε n. As a natural generalisation of random graphs and connectedness, we consider the binomial random k-uniform hypergraph Hk(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 ≤ j ≤ 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 Hk(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.