Threshold and hitting time for high-order connectedness in random hypergraphs

MaRDI QIDQ2629490zbMATH OpenFDO

Authors Oliver Cooley, Mihyun Kang, Christoph Koch

Publication date 6 July 2016

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07289, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i2p48

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

connectivityhitting timerandom hypergraphs

Mathematics Subject Classification ID

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

Abstract: We consider the following definition of connectivity in $k$-uniform hypergraphs: 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 determine the threshold at which the random $k$-uniform hypergraph with edge probability $p$ becomes $j$-connected with high probability. We also deduce a hitting time result for the random hypergraph process -- the hypergraph becomes $j$-connected at exactly the moment when the last isolated $j$-set disappears. This generalises well-known results for graphs.

Review text

Summary: We consider the following definition of connectedness in \(k\)-uniform hypergraphs: two \(j\)-sets (sets of \(j\) vertices) are \(j\)-connected if there is a walk of edges between them such that two consecutive edges intersect in at least \(j\) vertices. The hypergraph is \(j\)-connected if all \(j\)-sets are pairwise \(j\)-connected. We determine the threshold at which the random \(k\)-uniform hypergraph with edge probability \(p\) becomes \(j\)-connected with high probability. We also deduce a hitting time result for the random hypergraph process -- the hypergraph becomes \(j\)-connected at exactly the moment when the last isolated \(j\)-set disappears. This generalises the classical hitting time result of \textit{B. Bollobás} and \textit{A. Thomason} [ Ann. Discrete Math. 28, 47--97 (1985; Zbl 0588.05040)] for graphs.

Recommendations

• Evolution of high-order connected components in random hypergraphs
• On the strength of connectedness of a random hypergraph
• Largest components in random hypergraphs
• The size of the giant high-order component in random hypergraphs
• Connectivity of the linear uniform hypergraph process

Cites work

• scientific article; zbMATH DE number 3943863 (Why is no real title available?)
• scientific article; zbMATH DE number 52632 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Inside the critical window for cohomology of random \(k\)-complexes
• On the strength of connectedness of a random hypergraph
• Random graphs.
• The size of the giant component in random hypergraphs: a short proof

Cited in

(8)

• Homological connectedness of random hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Connectivity of the linear uniform hypergraph process
• scientific article; zbMATH DE number 647643 (Why is no real title available?)
• Jigsaw percolation on random hypergraphs
• Cohomology groups of non-uniform random simplicial complexes
• Ranking Inferences Based on the Top Choice of Multiway Comparisons

This page was built for publication: Threshold and hitting time for high-order connectedness in random hypergraphs

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