Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)

 
 

 

Critical percolation on random regular graphs


Authors: Felix Joos and Guillem Perarnau
Journal: Proc. Amer. Math. Soc.
MSC (2010): Primary 05C80, 05C82
DOI: https://doi.org/10.1090/proc/14021
Published electronically: March 20, 2018
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Noga Alon, Itai Benjamini, and Alan Stacey, Percolation on finite graphs and isoperimetric inequalities, Ann. Probab. 32 (2004), no. 3A, 1727-1745. MR 2073175
  • [2] 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
  • [3] 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
  • [4] 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
  • [5] 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 0125031
  • [6] N. Fountoulakis, Percolation on sparse random graphs with given degree sequence, Internet Math. 4 (2007), no. 4, 329-356. MR 2522948
  • [7] N. Fountoulakis, Percolation on sparse random graphs with given degree sequence, Internet Math. 4 (2007), no. 4, 329-356. MR 2522948
  • [8] 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
  • [9] Geoffrey R. Grimmett and David R. Stirzaker, Probability and random processes, 3rd ed., Oxford University Press, New York, 2001. MR 2059709
  • [10] Svante Janson, On percolation in random graphs with given vertex degrees, Electron. J. Probab. 14 (2009), no. 5, 87-118. MR 2471661
  • [11] 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
  • [12] 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
  • [13] 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
  • [14] 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
  • [15] Colin McDiarmid, Connectivity for random graphs from a weighted bridge-addable class, Electron. J. Combin. 19 (2012), no. 4, Paper 53, 20. MR 3007188
  • [16] Brendan D. McKay, Asymptotics for symmetric 0-$ 1$ matrices with prescribed row sums, Ars Combin. 19 (1985), no. A, 15-25. MR 790916
  • [17] 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
  • [18] Asaf Nachmias, Mean-field conditions for percolation on finite graphs, Geom. Funct. Anal. 19 (2009), no. 4, 1171-1194. MR 2570320
  • [19] Asaf Nachmias and Yuval Peres, Critical random graphs: diameter and mixing time, Ann. Probab. 36 (2008), no. 4, 1267-1286. MR 2435849
  • [20] Asaf Nachmias and Yuval Peres, Critical percolation on random regular graphs, Random Structures Algorithms 36 (2010), no. 2, 111-148. MR 2583058
  • [21] Asaf Nachmias and Yuval Peres, The critical random graph, with martingales, Israel J. Math. 176 (2010), 29-41. MR 2653185
  • [22] Boris Pittel, Edge percolation on a random regular graph of low degree, Ann. Probab. 36 (2008), no. 4, 1359-1389. MR 2435852
  • [23] Oliver Riordan, The phase transition in the configuration model, Combin. Probab. Comput. 21 (2012), no. 1-2, 265-299. MR 2900063
  • [24] 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

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 05C80, 05C82

Retrieve articles in all journals with MSC (2010): 05C80, 05C82


Additional Information

Felix Joos
Affiliation: School of Mathematics, University of Birmingham, Birmingham, United Kingdom
Email: f.joos@bham.ac.uk

Guillem Perarnau
Affiliation: School of Mathematics, University of Birmingham, Birmingham, United Kingdom
Email: g.perarnau@bham.ac.uk

DOI: https://doi.org/10.1090/proc/14021
Received by editor(s): March 27, 2017
Received by editor(s) in revised form: October 16, 2017, and November 13, 2017
Published electronically: March 20, 2018
Additional Notes: The first author was supported by the EPSRC, grant no. EP/M009408/1.
Communicated by: David Levin
Article copyright: © Copyright 2018 American Mathematical Society

American Mathematical Society