Critical percolation on random regular graphs

Joos, Felix; Perarnau, Guillem

doi:10.1090/proc/14021

Critical percolation on random regular graphs
HTML articles powered by AMS MathViewer

by Felix Joos and Guillem Perarnau PDF

Proc. Amer. Math. Soc. 146 (2018), 3321-3332 Request permission

Abstract:

We show that for all $d\in \{3,\ldots ,n-1\}$ the size of the largest component of a random $d$-regular graph on $n$ vertices around the percolation threshold $p=1/(d-1)$ is $\Theta (n^{2/3})$, with high probability. This extends known results for fixed $d\geq 3$ and for $d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. As a corollary, for the largest component of the percolated random $d$-regular graph, we also determine the diameter and the mixing time of the lazy random walk. In contrast to previous approaches, our proof is based on a simple application of the switching method.

References

Noga Alon, Itai Benjamini, and Alan Stacey, Percolation on finite graphs and isoperimetric inequalities, Ann. Probab. 32 (2004), no. 3A, 1727–1745. MR 2073175, DOI 10.1214/009117904000000414
Béla Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), no. 4, 311–316. MR 595929, DOI 10.1016/S0195-6698(80)80030-8
Béla Bollobás and Oliver Riordan, An old approach to the giant component problem, J. Combin. Theory Ser. B 113 (2015), 236–260. MR 3343756, DOI 10.1016/j.jctb.2015.03.002
Christian Borgs, Jennifer T. Chayes, Remco van der Hofstad, Gordon Slade, and Joel Spencer, Random subgraphs of finite graphs. I. The scaling window under the triangle condition, Random Structures Algorithms 27 (2005), no. 2, 137–184. MR 2155704, DOI 10.1002/rsa.20051
P. Erdős and A. Rényi, On the evolution of random graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 5 (1960), 17–61 (English, with Russian summary). MR 125031
N. Fountoulakis, Percolation on sparse random graphs with given degree sequence, Internet Math. 4 (2007), no. 4, 329–356. MR 2522948
N. Fountoulakis, Percolation on sparse random graphs with given degree sequence, Internet Math. 4 (2007), no. 4, 329–356. MR 2522948
Andreas Goerdt, The giant component threshold for random regular graphs with edge faults, Theoret. Comput. Sci. 259 (2001), no. 1-2, 307–321. MR 1832797, DOI 10.1016/S0304-3975(00)00015-3
Geoffrey R. Grimmett and David R. Stirzaker, Probability and random processes, 3rd ed., Oxford University Press, New York, 2001. MR 2059709
Svante Janson, On percolation in random graphs with given vertex degrees, Electron. J. Probab. 14 (2009), no. 5, 87–118. MR 2471661, DOI 10.1214/EJP.v14-603
Felix Joos, Guillem Perarnau, Dieter Rautenbach, and Bruce Reed, How to determine if a random graph with a fixed degree sequence has a giant component, 57th Annual IEEE Symposium on Foundations of Computer Science—FOCS 2016, IEEE Computer Soc., Los Alamitos, CA, 2016, pp. 695–703. MR 3631032, DOI 10.1109/FOCS.2016.79
Michael Krivelevich and Benny Sudakov, The phase transition in random graphs: a simple proof, Random Structures Algorithms 43 (2013), no. 2, 131–138. MR 3085765, DOI 10.1002/rsa.20470
Michael Krivelevich, Benny Sudakov, Van H. Vu, and Nicholas C. Wormald, Random regular graphs of high degree, Random Structures Algorithms 18 (2001), no. 4, 346–363. MR 1839497, DOI 10.1002/rsa.1013
Tomasz Łuczak, Boris Pittel, and John C. Wierman, The structure of a random graph at the point of the phase transition, Trans. Amer. Math. Soc. 341 (1994), no. 2, 721–748. MR 1138950, DOI 10.1090/S0002-9947-1994-1138950-5
Colin McDiarmid, Connectivity for random graphs from a weighted bridge-addable class, Electron. J. Combin. 19 (2012), no. 4, Paper 53, 20. MR 3007188
Brendan D. McKay, Asymptotics for symmetric $0$-$1$ matrices with prescribed row sums, Ars Combin. 19 (1985), no. A, 15–25. MR 790916
Brendan D. McKay and Nicholas C. Wormald, Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2})$, Combinatorica 11 (1991), no. 4, 369–382. MR 1137769, DOI 10.1007/BF01275671
Asaf Nachmias, Mean-field conditions for percolation on finite graphs, Geom. Funct. Anal. 19 (2009), no. 4, 1171–1194. MR 2570320, DOI 10.1007/s00039-009-0032-4
Asaf Nachmias and Yuval Peres, Critical random graphs: diameter and mixing time, Ann. Probab. 36 (2008), no. 4, 1267–1286. MR 2435849, DOI 10.1214/07-AOP358
Asaf Nachmias and Yuval Peres, Critical percolation on random regular graphs, Random Structures Algorithms 36 (2010), no. 2, 111–148. MR 2583058, DOI 10.1002/rsa.20277
Asaf Nachmias and Yuval Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010), 29–41. MR 2653185, DOI 10.1007/s11856-010-0019-8
Boris Pittel, Edge percolation on a random regular graph of low degree, Ann. Probab. 36 (2008), no. 4, 1359–1389. MR 2435852, DOI 10.1214/07-AOP361
Oliver Riordan, The phase transition in the configuration model, Combin. Probab. Comput. 21 (2012), no. 1-2, 265–299. MR 2900063, DOI 10.1017/S0963548311000666
N. C. Wormald, Models of random regular graphs, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 239–298. MR 1725006