Exploring hypergraphs with martingales |
| |
| Authors: | Béla Bollobás Oliver Riordan |
| |
| Institution: | 1. Department of Pure Mathematics and Mathematical Statistics, Cambridge, UK;2. Department of Mathematical Sciences, University of Memphis, Memphis, Tennessee;3. Mathematical Institute, University of Oxford, Radcliffe Observatory Quarter, Oxford, UK |
| |
| 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 L1 of vertices in the largest component  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 L1, and joint asymptotic normality of L1 and the number M1 of edges of  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 |
| |
| Keywords: | random hypergraph phase transition martingale |
|
|
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 L1, and joint asymptotic normality of L1 and the number M1 of edges of 
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