Critical percolation on random regular graphs

DOI10.1090/PROC/14021MaRDI QIDQ4563646zbMATHOpenAlexFDO

Authors Felix Joos, Guillem Perarnau

Publication date 4 June 2018

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.03639

zbMATH Keywords

percolationrandom regular graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Abstract: We show that for all $din3,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 $dgeq3$ 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.

Recommendations

• Critical percolation on random regular graphs
• Edge percolation on a random regular graph of low degree
• A note about critical percolation on finite graphs
• Percolation with small clusters on random graphs
• The phase transition in the configuration model

Cites work

• scientific article; zbMATH DE number 6680986 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3906527 (Why is no real title available?)
• scientific article; zbMATH DE number 1342092 (Why is no real title available?)
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• An old approach to the giant component problem
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Connectivity for random graphs from a weighted bridge-addable class
• Critical percolation on random regular graphs
• Critical random graphs: Diameter and mixing time
• Edge percolation on a random regular graph of low degree
• Mean-field conditions for percolation on finite graphs
• On percolation in random graphs with given vertex degrees
• Percolation on finite graphs and isoperimetric inequalities.
• Percolation on sparse random graphs with given degree sequence
• Probability and random processes.
• Random regular graphs of high degree
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• The Structure of a Random Graph at the Point of the Phase Transition
• The critical random graph, with martingales
• The giant component threshold for random regular graphs with edge faults H. Prodinger
• The phase transition in random graphs: a simple proof
• The phase transition in the configuration model

Cited in

(21)

• Dynamics of random graphs with bounded degrees
• Upper bounds for the largest component in critical inhomogeneous random graphs
• The probability of unusually large components for critical percolation on random \(d\)-regular graphs
• A note about critical percolation on finite graphs
• The unreasonable effectiveness of martingales
• An elementary approach to component sizes in critical random graphs
• Critical percolation on random regular graphs
• Percolation on dense random graphs with given degrees
• Percolating level sets of the adjacency eigenvectors of \(d\)-regular graphs
• On percolation in random graphs with given vertex degrees
• The critical point of \(k\)-clique percolation in the Erdős-Rényi graph
• Edge percolation on a random regular graph of low degree
• Critical percolation on scale-free random graphs: new universality class for the configuration model
• scientific article; zbMATH DE number 3976062 (Why is no real title available?)
• Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs
• Asymptotics in percolation on high-girth expanders
• Critical window for the vacant set left by random walk on random regular graphs
• Mean-field conditions for percolation on finite graphs
• Cycle structure of percolation on high-dimensional tori
• Percolation with small clusters on random graphs
• The phase transition in site percolation on pseudo-random graphs

This page was built for publication: Critical percolation on random regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4563646)