Law of the iterated logarithm for random graphs. Issue 1 (12th July 2018)

• Record Type: Journal Article
• Authors: Ferber, Asaf; Montealegre, Daniel; Vu, Van
• Is Part Of: Random structures & algorithms. Volume 54:Issue 1(2019)
• Page Start: 3
• Page End: 38
• Publication Date: 2018-07-12
• Subjects: central limit theorem -- distribution -- Hamilton cycles -- perfect matchings -- small subgraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20784
• Languages: English
• ISSNs: 1042-9832

Abstract

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.