Subcritical random hypergraphs, high-order components, and hypertrees

DOI10.1137/1.9781611975505.12MaRDI QIDQ5195239zbMATH OpenOpenAlexFDO

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)

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

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.

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

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)