Exploring hypergraphs with martingales

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 $L_1$ of vertices in the largest component $C$ of the random $r$-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 $L_1$, and joint asymptotic normality of $L_1$ and the number $M_1$ of edges of $C$. These results are used in a separate paper "Counting connected hypergraphs via the probabilistic method" to enumerate sparsely connected hypergraphs asymptotically.

32 pages; significantly expanded presentation. To appear in Random Structures and Algorithms

References in corpus (3)

• Component sizes of the random graph outside the scaling window
• Asymptotic normality of the size of the giant component in a random hypergraph
• Counting connected hypergraphs via the probabilistic method

Cited by in corpus (1)

• On the critical probability in percolation