Exploring hypergraphs with martingales1. Issue 3 (21st November 2016)

• Record Type: Journal Article
• Authors: Bollobás, Béla; Riordan, Oliver
• Is Part Of: Random structures & algorithms. Volume 50:Issue 3(2017)
• Page Start: 325
• Page End: 352
• Publication Date: 2016-11-21
• Subjects: random hypergraph -- phase transition -- martingale; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20678
• Languages: English
• ISSNs: 1042-9832

Abstract

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