Giant vacant component left by a random walk in a random \(d\)-regular graph

DOI10.1214/10-AIHP407zbMath1267.05237arXiv1012.5117OpenAlexW2054368400MaRDI QIDQ1944664

David Windisch, Jiří Černý, Augusto Q. Teixeira

Publication date: 26 March 2013

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

phase transitionsimple random walkregular graphtrajectorythresholdexpandersvacant setlargest componenttree-like structurefixed positive parameterpercolative propertiesrandom interlacement model

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Random walks, random surfaces, lattice animals, etc. in equilibrium statistical mechanics (82B41) Random walks on graphs (05C81)

Related Items (18)

Soft local times and decoupling of random interlacements ⋮ Giant component for the supercritical level‐set percolation of the Gaussian free field on regular expander graphs ⋮ On the critical parameter of interlacement percolation in high dimension ⋮ Anatomy of a Gaussian giant: supercritical level-sets of the free field on regular graphs ⋮ Random interlacements and amenability ⋮ Unnamed Item ⋮ Concentration of the Clock Process Normalisation for the Metropolis Dynamics of the REM ⋮ Aging of the Metropolis dynamics on the random energy model ⋮ Component structure of the vacant set induced by a random walk on a random graph ⋮ Large deviations for occupation time profiles of random interlacements ⋮ Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk ⋮ On scaling limits and Brownian interlacements ⋮ Local picture and level-set percolation of the Gaussian free field on a large discrete torus ⋮ Level-set percolation of the Gaussian free field on regular graphs II: finite expanders ⋮ A lower bound on the critical parameter of interlacement percolation in high dimension ⋮ Level-set percolation of the Gaussian free field on regular graphs. I. Regular trees ⋮ Critical window for the vacant set left by random walk on random regular graphs ⋮ Phase transition for the vacant set left by random walk on the giant component of a random graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the critical parameter of interlacement percolation in high dimension
• Random walks on discrete cylinders and random interlacements
• Edge percolation on a random regular graph of low degree
• Vacant set of random interlacements and percolation
• Cutoff phenomena for random walks on random regular graphs
• Upper bound on the disconnection time of discrete cylinders and random interlacements
• Random walk on a discrete torus and random interlacements
• Interlacement percolation on transient weighted graphs
• On the domination of a random walk on a discrete cylinder by random interlacements
• Minimization algorithms and random walk on the d-cube
• Ramanujan graphs
• On the second eigenvalue and random walks in random \(d\)-regular graphs
• Inequalities for rare events in time-reversible Markov chains. II
• Large deviation rates for branching processes. I: Single type case
• Percolation on finite graphs and isoperimetric inequalities.
• Giant component and vacant set for random walk on a discrete torus
• On the disconnection of a discrete cylinder by a random walk
• Critical percolation on random regular graphs
• On the fragmentation of a torus by random walk
• A proof of Alon’s second eigenvalue conjecture and related problems
• Percolation for the vacant set of random interlacements
• Random subgraphs of finite graphs: I. The scaling window under the triangle condition
• Probability

This page was built for publication: Giant vacant component left by a random walk in a random \(d\)-regular graph