A short proof of a central limit theorem for the order of the giant component and k-core

2025/06/13 by Anastos, Michael, Erde, Joshua, Kang, Mihyun +1
#05C80 #60F05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2506.11651

Abstract

In this note we outline a new and simple approach to proving central limit theorems for various 'global' graph parameters which have robust 'local' approximations, using the Efron--Stein inequality, which relies on a combinatorial analysis of the stability of these approximations under resampling an edge. As an application, we give short proofs of a central limit theorem for the order of the giant component and of the k-core for sparse random graphs.

Citations

• The law of the circumference of sparse binomial random graphs
• A central limit theorem for the matching number of a sparse random graph
• The Exact Rank of Sparse Random Graphs
• A note on long cycles in sparse random graphs
• Core forging and local limit theorems for the k-core of random graphs
• How does the core sit inside the mantle?

Related

• Core forging and local limit theorems for the k-core of random graphs
• A Central Limit Theorem for Functions on Weighted Sparse Inhomogeneous Random Graphs
• Locality via Global Ties: Stability of the 2-Core Against Misspecification
• A simple solution to the k-core problem
• The giant in random graphs is almost local