Critical percolation on random regular graphs

DOI10.1090/PROC/14021zbMATH Open1388.05170arXiv1703.03639OpenAlexW2595513744MaRDI QIDQ4563646FDOQ4563646

Authors: Felix Joos, Guillem Perarnau 

Publication date: 4 June 2018

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

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.

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

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

zbMATH Keywords

percolationrandom regular graph

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (21)

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

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)