Exploring hypergraphs with martingales

DOI10.1002/RSA.20678MaRDI QIDQ5739093zbMATH OpenOpenAlexFDO

Authors Béla Bollobás, Oliver Riordan

Publication date 2 June 2017

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

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

zbMATH Keywords

phase transitionmartingalerandom hypergraph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Hypergraphs (05C65)

Abstract: Recently, we adapted exploration and martingale arguments of Nachmias and Peres, in turn based on ideas of Martin-L"of, Karp and Aldous, to prove asymptotic normality of the number $L_1$ of vertices in the largest component $C$ of the random $r$-uniform hypergraph throughout the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of $L_1$, and joint asymptotic normality of $L_1$ and the number $M_1$ of edges of $C$. These results are used in a separate paper "Counting connected hypergraphs via the probabilistic method" to enumerate sparsely connected hypergraphs asymptotically.

Recommendations

• Asymptotic normality of the size of the giant component in a random hypergraph
• The phase transition in a random hypergraph
• Counting dense connected hypergraphs via the probabilistic method
• Local Limit Theorems for the Giant Component of Random Hypergraphs
• Local limit theorems for the giant component of random hypergraphs

Cites work

• scientific article; zbMATH DE number 4060392 (Why is no real title available?)
• Asymptotic normality of the size of the giant component in a random hypergraph
• Asymptotic normality of the size of the giant component via a random walk
• Brownian excursions, critical random graphs and the multiplicative coalescent
• Component sizes of the random graph outside the scaling window
• Component structure in the evolution of random hypergraphs
• Counting connected graphs inside-out
• Counting connected hypergraphs via the probabilistic method
• Large‐deviations/thermodynamic approach to percolation on the complete graph
• Local limit theorems for the giant component of random hypergraphs
• Some Theorems on Distribution Functions
• Some large deviation results for sparse random graphs
• Symmetric sampling procedures, general epidemic processes and their threshold limit theorems
• The order of the giant component of random hypergraphs
• The phase transition in a random hypergraph
• The phase transition in the configuration model
• The transitive closure of a random digraph

Cited in

(8)

• Asymptotic normality of the size of the giant component in a random hypergraph
• Counting connected hypergraphs via the probabilistic method
• On the critical probability in percolation
• Phase transitions in graphs on orientable surfaces
• Subcritical random hypergraphs, high-order components, and hypertrees
• Hitting times, commute times, and cover times for random walks on random hypergraphs
• Phase transition in cohomology groups of non-uniform random simplicial complexes
• Loose cores and cycles in random hypergraphs

This page was built for publication: Exploring hypergraphs with martingales

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