Asymptotic normality of the size of the giant component via a random walk

DOI10.1016/J.JCTB.2011.04.003zbMATH Open1237.05192arXiv1010.4595OpenAlexW3104497048MaRDI QIDQ765189FDOQ765189

Béla Bollobás, Oliver Riordan

Publication date: 19 March 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: In this paper we give a simple new proof of a result of Pittel and Wormald concerning the asymptotic value and (suitably rescaled) limiting distribution of the number of vertices in the giant component of $G(n,p)$ above the scaling window of the phase transition. Nachmias and Peres used martingale arguments to study Karp's exploration process, obtaining a simple proof of a weak form of this result. We use slightly different martingale arguments to obtain a much sharper result with little extra work.

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

Recommendations

• Asymptotic normality of the size of the giant component in a random hypergraph
• On the normality of giant components
• A new approach to the giant component problem
• On the fluctuations of the giant component
• A simple branching process approach to the phase transition in \(G_{n,p}\)

zbMATH Keywords

random walknormal approximationrandom graphsgiant component

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Cites Work

• Brownian excursions, critical random graphs and the multiplicative coalescent
• Title not available (Why is that?)
• Martingale Central Limit Theorems
• The transitive closure of a random digraph
• Component sizes of the random graph outside the scaling window
• Counting connected graphs inside-out
• Symmetric sampling procedures, general epidemic processes and their threshold limit theorems
• On tree census and the giant component in sparse random graphs
• On the Probability of Connectedness of a Random Graph $\mathcal{G}_m (t)$

Cited In (16)

• Exploring hypergraphs with martingales
• Asymptotic normality of the size of the giant component in a random hypergraph
• Erdős-Rényi poissonized
• Asymptotic normality in random graphs with given vertex degrees
• A power law of order 1/4 for critical mean field Swendsen-Wang dynamics
• Chain-referral sampling on stochastic block models
• Phase transitions in graphs on orientable surfaces
• Asymptotic distribution of the numbers of vertices and arcs of the giant strong component in sparse random digraphs
• Aggregation models with limited choice and the multiplicative coalescent
• Respondent-driven sampling on sparse Erdös-Rényi graphs
• Local Limit Theorems for the Giant Component of Random Hypergraphs
• The probability of unusually large components for critical percolation on random \(d\)-regular graphs
• Central limit theorem for statistics of subcritical configuration models
• Unusually large components in near-critical Erdős–Rényi graphs via ballot theorems
• Central limit theorems in the configuration model
• The probability of unusually large components in the near-critical Erdős–Rényi graph

This page was built for publication: Asymptotic normality of the size of the giant component via a random walk

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