Law of the iterated logarithm for random graphs

Asaf Ferber, Daniel Montealegre, Van VuRandom Struct. Algorithms 2019 · DOI

TL;DR

This paper extends the classical Law of the Iterated Logarithm (LIL) from simple random variables to complex random graph and hypergraph structures. The authors prove LIL for the number of copies of fixed subgraphs, perfect matchings in bipartite graphs, and Hamiltonian cycles in random graphs and hypergraphs, revealing fundamental probabilistic behaviors in these intricate combinatorial objects.

What Problem Does This Paper Address?

The Law of the Iterated Logarithm (LIL) is a cornerstone of probability theory, describing the precise rate at which sums of independent and identically distributed (i.i.d.) random variables fluctuate. It states that the normalized sum of such variables, when scaled by the square root of twice the logarithm of the logarithm of n, converges to 1. While the Central Limit Theorem (CLT) has been extensively studied for various random graph and hypergraph models, the LIL, which provides a more refined understanding of fluctuations, has remained largely unexplored in this domain. This paper aims to bridge this gap by investigating the applicability of the LIL to counting problems in random graphs and hypergraphs, particularly for global structures like perfect matchings and Hamiltonian cycles, which are notoriously difficult to analyze.

Methods

The authors employ a combination of established probabilistic tools and novel techniques. Key methods include:

  • Janson's Inequality: Used for obtaining lower tail estimates for the number of subgraph copies.
  • Borel-Cantelli Lemma: Crucial for establishing that certain events occur infinitely often or only finitely often with probability 1, which is central to proving LIL.
  • Dependency Graphs and Concentration Bounds: The paper leverages Rinott's theorem on the CLT for sums of dependent random variables and develops new large deviation bounds for counting perfect matchings and Hamiltonian cycles. These bounds are critical for handling the dependencies inherent in graph structures.
  • Bregman-Minc Inequality: Used in the analysis of perfect matchings in bipartite graphs.
  • Combinatorial Counting and Estimation: The proofs involve intricate combinatorial arguments to bound the number of ways to form specific graph structures and to estimate variances and covariances.

A significant new ingredient is a large deviation bound for counting perfect matchings and Hamiltonian cycles, which the authors suggest could be of independent interest.

Datasets

Not discussed in the paper. The paper deals with theoretical models of random graphs and hypergraphs, not empirical datasets.

Key Insights and Ideas

  • LIL Extends to Complex Structures: The most striking insight is that the LIL, a property of simple sums of random variables, holds for complex counting functions in random graphs and hypergraphs. This suggests a deeper underlying probabilistic structure in these combinatorial objects than previously appreciated.
  • Global Structures Behave Differently: The LIL for the number of Hamiltonian cycles in k-uniform hypergraphs behaves differently for k ≥ 3 compared to k = 2 (graphs). For k ≥ 3, the count itself satisfies the LIL, whereas for k = 2, it's the logarithm of the count that satisfies the LIL. This is attributed to the smaller variance in hypergraphs due to less overlap between cycles.
  • Logarithm of Counts: For certain structures like perfect matchings in bipartite graphs and Hamiltonian cycles in graphs, the LIL applies to the logarithm of the count, not the count itself. This indicates that the fluctuations are multiplicative rather than additive.
  • New Large Deviation Bounds: The development of new large deviation bounds for perfect matchings and Hamiltonian cycles is a significant technical contribution, enabling the proofs of the LIL for these challenging problems.

Key Results

The paper establishes the Law of the Iterated Logarithm for several key counting problems in random graphs and hypergraphs:

  • Number of Copies of a Fixed Subgraph (H) in G(n,p): The number of copies of a fixed graph H in G(n,p) satisfies the LIL.
  • Number of Perfect Matchings in B(n,p): The logarithm of the number of perfect matchings in a random bipartite graph B(n,p) satisfies the LIL.
  • Number of Hamiltonian Cycles in G(n,p): The logarithm of the number of Hamiltonian cycles in a random graph G(n,p) satisfies the LIL.
  • Number of Hamiltonian Cycles in k-Uniform Hypergraphs H*(n,p):
    • For k ≥ 3, the number of Hamiltonian cycles itself satisfies the CLT.
  • For k ≥ 4, the number of Hamiltonian cycles satisfies the LIL. The case k = 3 is left as an open problem.

Limitations and Future Work

  • Fixed Edge Probability: The results are proven for a fixed edge probability p ∈ (0, 1). The authors note that extending these results to sparse random graphs (where p depends on n) is an interesting open problem, requiring the analysis of ranges of densities for which LIL holds.
  • Case k=3 for Hypergraphs: The LIL for Hamiltonian cycles in 3-uniform hypergraphs is left as an open problem.
  • Approximation of Mean and Variance: For some results (Theorems 1.4 and 1.5), the authors state that the expected value and variance of the normalized variables are unknown, and they conjecture that the constants used in the theorems are good approximations. Verifying these conjectures would be a natural next step.
  • Generalization to Other Structures: The paper motivates further research into the validity of LIL for other types of CLTs in random graph and hypergraph literature.

Summary updated

BibTeX
@article{ferber2019law,
  author = {Asaf Ferber and Daniel Montealegre and Van Vu},
  title = {{Law of the iterated logarithm for random graphs}},
  journal = {Random Struct. Algorithms},
  year = {2019},
  doi = {10.1002/rsa.20784},
}
Figure