Law of Iterated Logarithm for random graphs

2016/07/29 by Ferber, Asaf, Montealegre, Daniel, Vu, Van
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.08865

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 Pr [ \limsup_{n→ ∞} \frac ∑_i=1ⁿ t_i σ_n √ 2 log log n =1 ] =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 (CLT) and LIL for the number of Hamilton cycles.

Related

• A law of the iterated logarithm for iterated random walks, with application to random recursive trees
• Laws of the iterated logarithm for iterated perturbed random walks
• Super-logarithmic cliques in dense inhomogeneous random graphs
• On the law of the iterated logarithm and strong invariance principles in\n stochastic geometry
• On the law of the iterated logarithm under the sub-linear expectations