Phase transition for the vacant set left by random walk on the giant component of a random graph

DOI10.1214/13-AIHP596zbMATH Open1312.05126arXiv1308.2548OpenAlexW2963087671MaRDI QIDQ2346194FDOQ2346194

Authors: Tobias Wassmer 

Publication date: 29 May 2015

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

Abstract: We study the simple random walk on the giant component of a supercritical ErdH{o}s-R'enyi random graph on $n$ vertices, in particular the so-called vacant set at level $u$, the complement of the trajectory of the random walk run up to a time proportional to $u$ and $n$. We show that the component structure of the vacant set exhibits a phase transition at a critical parameter $u_{star}$: For $u<u_{star}$ the vacant set has with high probability a unique giant component of order $n$ and all other components small, of order at most $lo{g}^{7}n$, whereas for $u>u_{star}$ it has with high probability all components small. Moreover, we show that $u_{star}$ coincides with the critical parameter of random interlacements on a Poisson-Galton-Watson tree, which was identified in [Tas10].

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

Recommendations

• Component structure of the vacant set induced by a random walk on a random graph
• Component structure of the vacant set induced by a random walk on a random graph
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• Logarithmic components of the vacant set for random walk on a discrete torus
• Critical window for the vacant set left by random walk on random regular graphs

zbMATH Keywords

random walkphase transitionvacant setrandom interlacementsgiant componentErdős-Rényi random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Random walks on graphs (05C81)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Inequalities for rare events in time-reversible Markov chains. I.
• Vacant set of random interlacements and percolation
• Interlacement percolation on transient weighted graphs
• On the fragmentation of a torus by random walk
• From random walk trajectories to random interlacements
• Title not available (Why is that?)
• The scaling window for a random graph with a given degree sequence
• Giant component and vacant set for random walk on a discrete torus
• The mixing time of the giant component of a random graph
• Minimization algorithms and random walk on the d-cube
• Universality of trap models in the ergodic time scale
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• Random interlacements on Galton-Watson trees
• Critical window for the vacant set left by random walk on random regular graphs
• Component structure of the vacant set induced by a random walk on a random graph

Cited In (7)

• Local picture and level-set percolation of the Gaussian free field on a large discrete torus
• Giant vacant component left by a random walk in a random \(d\)-regular graph
• Critical window for the vacant set left by random walk on the configuration model
• A short proof of the phase transition for the vacant set of random interlacements
• Vacant sets and vacant nets: component structures induced by a random walk
• Component structure of the vacant set induced by a random walk on a random graph
• Component structure of the vacant set induced by a random walk on a random graph

This page was built for publication: Phase transition for the vacant set left by random walk on the giant component of a random graph

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