Premium
Law of the iterated logarithm for random graphs
Author(s) -
Ferber Asaf,
Montealegre Daniel,
Vu Van
Publication year - 2019
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20784
Subject(s) - mathematics , law of the iterated logarithm , combinatorics , random graph , logarithm , central limit theorem , discrete mathematics , random variable , iterated logarithm , iterated function , graph , statistics , mathematical analysis
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.