A local central limit theorem for triangles in a random graph

Justin Gilmer, Swastik KoppartyRandom Struct. Algorithms 2016 · DOI

TL;DR

This paper establishes a precise "local" version of the central limit theorem for the number of triangles in a random graph. It shows that the probability of observing a specific number of triangles is well-approximated by a discrete Gaussian distribution, providing a powerful tool for understanding the fine-grained structure of random graphs.

What Problem Does This Paper Address?

The study of random graphs, particularly the Erdős-Rényi model $G(n,p)$, has a rich history. A fundamental question is understanding the distribution of subgraph counts, such as the number of triangles. While a "global" central limit theorem (CLT) states that the normalized number of triangles converges to a Gaussian distribution, this tells us about the overall shape of the distribution. However, for many applications, we need to know the exact probability of observing a specific number of triangles (a "local" CLT). This is particularly challenging when the edge probability $p$ is a fixed constant (not tending to 0 or 1). Previous methods, like the moment method or Stein's method, provide good global approximations but struggle to give precise bounds on individual probabilities in this regime. This paper aims to bridge this gap by providing a local limit theorem for triangle counts in $G(n,p)$ for fixed $p \in (0,1)$.

Methods

The core of the proof relies on a standard Fourier analytic strategy for local limit theorems. The authors analyze the characteristic function of the normalized triangle count, $\psi_n(t) = E[e^{it R_n}]$, where $R_n = (S_n - \mu_n) / \sigma_n$ is the normalized number of triangles. The goal is to show that $\psi_n(t)$ is close to the characteristic function of a standard Gaussian distribution ($e^{-t^2/2}$) over a relevant range of $t$.

The proof is divided into bounding $\psi_n(t)$ over different ranges of $t$:

  • Small $|t|$ (e.g., $|t| < A$ for a large constant $A$): This range is handled by appealing to the standard central limit theorem for triangle counts, which implies that the characteristic functions are close.
  • Intermediate $|t|$ (e.g., $A < |t| < n^{0.55}$): This is a crucial and technically involved part. The authors use a conditioning argument. They first reveal a subset of edges $F$ and then analyze the expectation of the characteristic function conditioned on $F$. This allows them to decompose the problem and use bounds on sums of independent random variables. They employ a clever strategy of partitioning edges into a "fixed" set $F$ and a "random" set $M$, and then conditioning on the structure of $F$.
  • Large $|t|$ (e.g., $n^{0.55} < |t| < \pi \sigma_n$): This range is handled by a different conditioning argument, where the vertex set is partitioned. The authors analyze the variance of certain random variables to show that the characteristic function decays rapidly.

The proof also leverages several lemmas, including bounds on Bernoulli random variables and concentration inequalities (like Chernoff and Chebyshev bounds).

Datasets

Not discussed in the paper. The paper deals with theoretical random graph models.

Key Insights and Ideas

  • Bridging Global and Local: The paper demonstrates that the techniques used for global CLTs can be adapted, with significant effort, to yield precise local limit theorems. This is a non-trivial extension.
  • The Power of Conditioning: The core technical innovation lies in the sophisticated use of conditioning arguments. By revealing parts of the graph structure and then analyzing the remaining random parts, the authors manage to control the characteristic function.
  • Decomposition Strategy: The strategy of partitioning edges or vertices and analyzing the resulting components is key to simplifying the complex dependencies in the triangle count.
  • Obstacle to Stronger Bounds: The authors explicitly mention that their current methods for large $|t|$ provide bounds that are not exponentially small, suggesting a potential barrier to achieving even stronger quantitative local limit laws.

Key Results

The main result is Theorem 2, which states that for a fixed edge probability $p \in (0,1)$, the distribution of the number of triangles $S_n$ in an Erdős-Rényi random graph $G(n,p)$ is pointwise approximated by a discrete Gaussian distribution. Specifically, for $k$ such that $|k - \mu_n| = O(n^2)$, the probability $Pr[S_n = k]$ is given by:

$$Pr[S_n = k] = \frac{1}{\sigma_n \sqrt{2\pi}} e^{-((k-\mu_n)/\sigma_n)^2/2} \pm O(1/n^2)$$

where $\mu_n = E[S_n]$ and $\sigma_n = \sqrt{Var[S_n]}$. This means the probability mass function is very close to that of a Gaussian distribution, up to an error term of order $O(1/n^2)$.

Limitations and Future Work

  • Quantitative Bounds: The paper acknowledges that the bounds for large $|t|$ are not as strong as they could be (not exponentially small). This is identified as a major obstacle for proving stronger quantitative local limit laws.
  • Generalization to Other Graphs: The authors conjecture that a similar local discrete Gaussian limit law should hold for the number of copies of any fixed connected graph $H$ in $G(n,p)$, provided $p$ is above the threshold probability for the appearance of $H$.
  • Joint Distributions: An interesting open question is to understand the joint distribution of subgraph counts for several fixed connected graphs.

This work provides a significant theoretical advance in understanding the fine structure of random graphs, with potential implications for areas that rely on precise probabilistic models of networks.

Summary updated

BibTeX
@article{gilmer2016local,
  author = {Justin Gilmer and Swastik Kopparty},
  title = {{A local central limit theorem for triangles in a random graph}},
  journal = {Random Struct. Algorithms},
  year = {2016},
  doi = {10.1002/rsa.20604},
}
Figure