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

DOI10.1214/13-AIHP596MaRDI QIDQ2346194zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1308.2548, https://projecteuclid.org/euclid.aihp/1428672690

zbMATH Keywords

Erdős-Rényi random graphgiant componentphase transitionrandom interlacementsrandom walkvacant set

Mathematics Subject Classification ID

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

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].

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

Cites work

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

Cited in

(7)

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

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)