Largest components in random hypergraphs

DOI10.1017/S096354831800010XMaRDI QIDQ4962589zbMATH OpenOpenAlexWikidataFDO

Authors Oliver Cooley, Mihyun Kang, Yury Person

Publication date 5 November 2018

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: In this paper we consider $j$-tuple-connected components in random $k$-uniform hypergraphs (the $j$-tuple-connectedness relation can be defined by letting two $j$-sets be connected if they lie in a common edge and consider the transitive closure; the case $j=1$ corresponds to the common notion of vertex-connectedness). We determine that the existence of a $j$-tuple-connected component containing $Theta(n^j)$ $j$-sets in random $k$-uniform hypergraphs undergoes a phase transition and show that the threshold occurs at edge probability $$. Our proof extends the recent short proof for the graph case by Krivelevich and Sudakov which makes use of a depth-first search to reveal the edges of a random graph. Our main original contribution is a "bounded degree lemma" which controls the structure of the component grown in the search process.

Recommendations

• The size of the giant component in random hypergraphs: a short proof
• Evolution of high-order connected components in random hypergraphs
• The size of the giant high-order component in random hypergraphs
• Component structure in the evolution of random hypergraphs
• The phase transition in a random hypergraph

Cites work

• Asymptotic normality of the size of the giant component in a random hypergraph
• Collapsibility and vanishing of top homology in random simplicial complexes
• Component behavior near the critical point of the random graph process
• Component structure in the evolution of random hypergraphs
• Cores in random hypergraphs and Boolean formulas
• Creation and Growth of Components in a Random Hypergraph Process
• Homological connectivity of random 2-complexes
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Local limit theorems for the giant component of random hypergraphs
• Random graphs.
• The critical random graph, with martingales
• The Evolution of Random Graphs
• The order of the giant component of random hypergraphs
• The phase transition in a random hypergraph
• The phase transition in random graphs: a simple proof
• The size of the giant high-order component in random hypergraphs
• The threshold for d-collapsibility in random complexes
• The triangle-free process
• When does the top homology of a random simplicial complex vanish?

Cited in

(18)

• Component structure in the evolution of random hypergraphs
• Forcing large tight components in 3-graphs
• The size of the giant component in random hypergraphs: a short proof
• Loose cores and cycles in random hypergraphs
• Generalizations and strengthenings of Ryser's conjecture
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Random simplicial complexes in the medial regime
• Threshold and hitting time for high-order connectedness in random hypergraphs
• Giant components in random graphs
• The order of the giant component of random hypergraphs
• scientific article; zbMATH DE number 3874387 (Why is no real title available?)
• The size of the giant high-order component in random hypergraphs
• Subcritical random hypergraphs, high-order components, and hypertrees
• Longest paths in random hypergraphs
• Subcritical random hypergraphs, high-order components, and hypertrees
• Random recursive hypergraphs
• Birth and growth of multicyclic components in random hypergraphs
• Paths, cycles and sprinkling in random hypergraphs

This page was built for publication: Largest components in random hypergraphs

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