A local limit theorem for the edge counts of random induced subgraphs of a random graph

2025/03/29 by Paul Balister, Emil Powierski, Balister, Paul +5
Mathematics · Physics and Astronomy · #Combinatorics (math.CO) #Complex Network Analysis Techniques #FOS: Mathematics #Limits and Structures in Graph Theory #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.2503.23164

openalex publication_date 2025/03/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Consider a `dense' Erdős--Rényi random graph model G=G_n,M with n vertices and M edges, where we assume the edge density M/\binomn2 is bounded away from 0 and 1. Fix k=k(n) with k/n bounded away from 0 and~1, and let S be a random subset of size k of the vertices of G. We show that with probability 1-exp(-n^Ω(1)), G satisfies both a central limit theorem and a local limit theorem for the empirical distribution of the edge count e(G[S]) of the subgraph of G induced by S, where the distribution is over uniform random choices of the k-set S.

Related

• Local limit theorem for joint subgraph counts
• A local central limit theorem for the number of triangles in a random graph
• On the probability that a random subtree is spanning
• A large deviation principle for the Erdős-Rényi uniform random graph
• Concentration of measure for the number of isolated vertices in the Erdős-Rényi random graph by size bias couplings