Subcritical random hypergraphs, high-order components, and hypertrees

DOI10.1137/1.9781611975505.12zbMATH Open1433.05236arXiv1810.08107OpenAlexW3092441220MaRDI QIDQ5195239FDOQ5195239

Authors: Oliver Cooley, W. Fang, Nicola Del Giudice, Mihyun Kang 

Publication date: 18 September 2019

Published in: 2019 Proceedings of the Sixteenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) (Search for Journal in Brave)

Abstract: In the binomial random graph $mathcalG(n,p)$, when $p$ changes from $(1-varepsilon)/n$ (subcritical case) to $1/n$ and then to $(1+varepsilon)/n$ (supercritical case) for $varepsilon>0$, with high probability the order of the largest component increases smoothly from $O(varepsilo{n}^{-2}log(varepsilo{n}^{3}n))$ to $Theta(n^{2/3})$ and then to $(1pmo(1))2varepsilonn$. As a natural generalisation 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 $1leqjleqk-1$, two sets of $j$ vertices are called emph{$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.

Full work available at URL: https://arxiv.org/abs/1810.08107

Recommendations

• Subcritical random hypergraphs, high-order components, and hypertrees
• The size of the giant high-order component in random hypergraphs
• Evolution of high-order connected components in random hypergraphs
• Largest components in random hypergraphs
• The phase transition in a random hypergraph

zbMATH Keywords

binomial random \(k\)-uniform hypergraphgiant \(j\)-connected component

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Hypergraphs (05C65)

Cited In (3)

• The size of the giant high-order component in random hypergraphs
• Subcritical random hypergraphs, high-order components, and hypertrees
• The distributions of the numbers of finite subgraphs in random nonhomogeneous hypergraphs

This page was built for publication: Subcritical random hypergraphs, high-order components, and hypertrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5195239)