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

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/\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ 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^{\Omega (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$.

25 pages