Back to Search
Start Over
Law of the iterated logarithm for random graphs.
- Source :
- Random Structures & Algorithms; Jan2019, Vol. 54 Issue 1, p3-38, 36p
- Publication Year :
- 2019
-
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 {ti}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. [ABSTRACT FROM AUTHOR]
- Subjects :
- RANDOM graphs
ITERATED integrals
RANDOM variables
HYPERGRAPHS
HAMILTON'S equations
Subjects
Details
- Language :
- English
- ISSN :
- 10429832
- Volume :
- 54
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Random Structures & Algorithms
- Publication Type :
- Academic Journal
- Accession number :
- 133192639
- Full Text :
- https://doi.org/10.1002/rsa.20784