The order of the giant component of random hypergraphs

DOI10.1002/RSA.20282MaRDI QIDQ3055882zbMATH OpenOpenAlexFDO

Authors Michael Behrisch, Amin Coja-Oghlan, Mihyun Kang

Publication date 10 November 2010

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

giant componentlimit theoremsrandom graphs and hypergraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We establish central and local limit theorems for the number of vertices in the largest component of a random $d$-uniform hypergraph $hnp$ with edge probability $$, where $(d-1{)}^{-1}+eps<c<infty$. The proof relies on a new, purely probabilistic approach, and is based on Stein's method as well as exposing the edges of $H_d(n,p)$ in several rounds.

Recommendations

• The size of the giant high-order component in random hypergraphs
• The size of the giant component in random hypergraphs: a short proof
• scientific article; zbMATH DE number 6303023
• Largest components in random hypergraphs
• The Size of the Giant Component of a Random Graph with a Given Degree Sequence
• Asymptotic normality of the size of the giant component in a random hypergraph
• scientific article; zbMATH DE number 970794
• Giant component in random multipartite graphs with given degree sequences
• Structure of large random hypergraphs
• On the structure of random hypergraphs

Cites work

• Component structure in the evolution of random hypergraphs
• Counting connected graphs and hypergraphs via the probabilistic method
• Counting connected graphs asymptotically
• Counting connected graphs inside-out
• Creation and Growth of Components in a Random Hypergraph Process
• On the fluctuations of the giant component
• On tree census and the giant component in sparse random graphs
• Random graph dynamics
• Stochastic processes in random graphs
• The average size of giant components between the double-jump
• The minimal spanning tree in a complete graph and a functional limit theorem for trees in a random graph
• The number of connected sparsely edged uniform hypergraphs
• The phase transition in a random hypergraph

Cited in

(26)

• Component structure in the evolution of random hypergraphs
• The phase transition in a random hypergraph
• The size of the giant component in random hypergraphs: a short proof
• Loose cores and cycles in random hypergraphs
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Local limit theorems via Landau-Kolmogorov inequalities
• Critical random hypergraphs: the emergence of a giant set of identifiable vertices
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• On the normality of giant components
• Asymptotic normality of the size of the giant component in a random hypergraph
• Evolution of high-order connected components in random hypergraphs
• Local Limit Theorems for the Giant Component of Random Hypergraphs
• Largest components in random hypergraphs
• Subcritical random hypergraphs, high-order components, and hypertrees
• Phase transitions in graphs on orientable surfaces
• The phase transition in multitype binomial random graphs
• Counting connected hypergraphs via the probabilistic method
• Local limit theorems for the giant component of random hypergraphs
• Exploring hypergraphs with martingales
• A local central limit theorem for triangles in a random graph
• scientific article; zbMATH DE number 7651160 (Why is no real title available?)
• Birth and growth of multicyclic components in random hypergraphs
• Local limit theorems for subgraph counts
• Connectivity of random hypergraphs with a given hyperedge size distribution
• The process of fluctuations of the giant component of an Erdős-Rényi graph
• Exploring the sharp propagation connectivity threshold in hypergraphs

This page was built for publication: The order of the giant component of random hypergraphs

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