Exploring hypergraphs with martingales1. Issue 3 (21st November 2016) - Bollobás, Béla; Riordan, Oliver
ABSTRACT: Recently, in [Random Struct Algorithm 41 (2012), 441–450] we adapted exploration and martingale arguments of Nachmias and Peres [ALEA Lat Am J Probab Math Stat 3 (2007), 133–142], in turn based on ideas of Martin‐Löf [J Appl Probab 23 (1986), 265–282], Karp [Random Struct Alg 1 (1990), 73–93] and Aldous [Ann Probab 25 (1997), 812–854], to prove asymptotic normality of the number L 1 of vertices in the largest component L 1 of the random r ‐uniform hypergraph in 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 L 1 in the sparsely supercritical case. These results are used in [Combin Probab Comput 25 (2016), 21–75], where we enumerate sparsely connected hypergraphs asymptotically. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 50, 325–352, 2017