Law of the iterated logarithm for random graphs. Issue 1 (12th July 2018) - Ferber, Asaf; Montealegre, Daniel; Vu, Van
Abstract: A milestone in probability theory is the law of the iterated logarithm (LIL), proved by Khinchin and independently by Kolmogorov in the 1920s, which asserts that for iid random variables t i i = 1 ∞ with mean 0 and variance 1 In this paper we prove that LIL holds for various functionals of random graphs and hypergraphs models. We first prove LIL for the number of copies of a fixed subgraph H . Two harder results concern the number of global objects: perfect matchings and Hamiltonian cycles. The main new ingredient in these results is a large deviation bound, which may be of independent interest. For random k ‐uniform hypergraphs, we obtain the Central Limit Theorem and LIL for the number of Hamilton cycles.