Exploring hypergraphs with martingales
arXiv:1403.6558 · doi:10.1002/rsa.20678
Abstract
Recently, we adapted exploration and martingale arguments of Nachmias and Peres, in turn based on ideas of Martin-Löf, Karp and Aldous, to prove asymptotic normality of the number of vertices in the largest component of the random -uniform hypergraph throughout the supercritical regime. In this paper we take these arguments further to prove two new results: strong tail bounds on the distribution of , and joint asymptotic normality of and the number of edges of . These results are used in a separate paper "Counting connected hypergraphs via the probabilistic method" to enumerate sparsely connected hypergraphs asymptotically.
arXiv comment32 pages; significantly expanded presentation. To appear in Random Structures and Algorithms
References in corpus (7)
- The phase transition in the configuration model
- Component sizes of the random graph outside the scaling window
- Asymptotic normality of the size of the giant component in a random hypergraph
- The Order of the Giant Component of Random Hypergraphs
- Asymptotic normality of the size of the giant component via a random walk
- Large-deviations/thermodynamic approach to percolation on the complete graph
- Counting connected hypergraphs via the probabilistic method