Evolution of high-order connected components in random hypergraphs

DOI10.1016/J.ENDM.2015.06.077MaRDI QIDQ322325zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Mihyun Kang, Christoph Koch

Publication date 14 October 2016

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

zbMATH Keywords

phase transitionhitting timerandom hypergraphsgiant componenthigh-order connectivity

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Connectivity (05C40) Hypergraphs (05C65)

Abstract: We consider high-order connectivity in $k$-uniform hypergraphs defined as follows: Two $j$-sets are $j$-connected if there is a walk of edges between them such that two consecutive edges intersect in at least $j$ vertices. We describe the evolution of $j$-connected components in the $k$-uniform binomial random hypergraph $mathcal{H}^k(n,p)$. In particular, we determine the asymptotic size of the giant component shortly after its emergence and establish the threshold at which the $mathcal{H}^k(n,p)$ becomes $j$-connected with high probability. We also obtain a hitting time result for the related random hypergraph process ${mathcal{H}^k(n,M)}_M$ -- the hypergraph becomes $j$-connected exactly at the moment when the last isolated $j$-set disappears. This generalises well-known results for graphs and vertex-connectivity in hypergraphs.

Recommendations

• Component structure in the evolution of random hypergraphs
• Connected components and evolution of random graphs: An algebraic approach
• Component evolution in random intersection graphs
• Component evolution in general random intersection graphs
• Component evolution in general random intersection graphs
• scientific article; zbMATH DE number 3168330
• The Evolution of Random Graphs
• scientific article; zbMATH DE number 1792101
• scientific article; zbMATH DE number 3173143
• scientific article; zbMATH DE number 3966129

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Asymptotic normality of the size of the giant component in a random hypergraph
• Component behavior near the critical point of the random graph process
• Component structure in the evolution of random hypergraphs
• The Evolution of Random Graphs
• The order of the giant component of random hypergraphs
• The phase transition in a random hypergraph

Cited in

(9)

• Threshold and hitting time for high-order connectedness in random hypergraphs
• Largest components in random hypergraphs
• The size of the giant component in random hypergraphs: a short proof
• The size of the giant high-order component in random hypergraphs
• Connectivity of random hypergraphs with a given hyperedge size distribution
• Creation and Growth of Components in a Random Hypergraph Process
• Subcritical random hypergraphs, high-order components, and hypertrees
• Connectivity of the linear uniform hypergraph process
• Subcritical random hypergraphs, high-order components, and hypertrees

This page was built for publication: Evolution of high-order connected components in random hypergraphs

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