Component structure of the vacant set induced by a random walk on a random graph
From MaRDI portal
(Redirected from Publication:4909198)
Abstract: We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Gamma(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_{n,p} (above the connectivity threshold) and for random regular graphs G_r, r geq 3, the graph Gamma(t) undergoes a phase transition in the sense of the well-known Erdos-Renyi phase transition. Thus for t leq (1-epsilon)t^*, there is a unique giant component, plus components of size O(log n), and for t geq (1+epsilon)t^* all components are of size O(log n). For G_{n,p} and G_r we give the value of t^*, and the size of Gamma(t). For G_r, we also give the degree sequence of Gamma(t), the size of the giant component (if any) of Gamma(t) and the number of tree components of Gamma(t) of a given size k=O(log n). We also show that for random digraphs D_{n,p} above the strong connectivity threshold, there is a similar directed phase transition. Thus for tleq (1-epsilon)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for tgeq (1+epsilon)t^* all strongly connected components are of size O(log n).
Recommendations
- 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
- Phase transition for the vacant set left by random walk on the giant component of a random graph
- Giant vacant component left by a random walk in a random \(d\)-regular graph
- Giant component and vacant set for random walk on a discrete torus
Cites work
- A critical point for random graphs with a given degree sequence
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- A proof of Alon’s second eigenvalue conjecture and related problems
- 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 3934150 (Why is no real title available?)
- scientific article; zbMATH DE number 6297796 (Why is no real title available?)
- scientific article; zbMATH DE number 3059214 (Why is no real title available?)
- Logarithmic components of the vacant set for random walk on a discrete torus
- Random minimum length spanning trees in regular graphs
- Stationary distribution and cover time of random walks on random digraphs
- The asymptotic number of labeled graphs with given degree sequences
- The Cover Time of Random Regular Graphs
- The cover time of the giant component of a random graph
- The Size of the Giant Component of a Random Graph with a Given Degree Sequence
- The transitive closure of a random digraph
Cited in
(12)- Giant vacant component left by a random walk in a random \(d\)-regular graph
- Level-set percolation of the Gaussian free field on regular graphs II: finite expanders
- Phase transition for the vacant set left by random walk on the giant component of a random graph
- Giant component and vacant set for random walk on a discrete torus
- A note on the vacant set of random walks on the hypercube and other regular graphs of high degree
- Critical window for the vacant set left by random walk on random regular graphs
- On the fragmentation of a torus by random walk
- Critical window for the vacant set left by random walk on the configuration model
- Geometry of the vacant set left by random walk on random graphs, Wright's constants, and critical random graphs with prescribed degrees
- 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
- Giant component for the supercritical level‐set percolation of the Gaussian free field on regular expander graphs
This page was built for publication: Component structure of the vacant set induced by a random walk on a random graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909198)
