Vacant Sets and Vacant Nets: Component Structures Induced by a Random Walk

DOI10.1137/14097937XzbMath1329.05261arXiv1404.4403OpenAlexW1913940382WikidataQ57401407 ScholiaQ57401407MaRDI QIDQ5743552

Colin Cooper, Alan M. Frieze

Publication date: 5 February 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random regular graphsrandom walkvacant setvacant net

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random walks on graphs (05C81)

Related Items

The cover time of a biased random walk on a random cubic graph ⋮ Random walk on sparse random digraphs ⋮ Unnamed Item ⋮ The cover time of a biased random walk on a random regular graph of odd degree

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The cover times of random walks on random uniform hypergraphs
• Logarithmic components of the vacant set for random walk on a discrete torus
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• The asymptotic number of labeled graphs with given degree sequences
• 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
• Critical window for the vacant set left by random walk on random regular graphs
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• The cover time of the giant component of a random graph
• A proof of Alon’s second eigenvalue conjecture and related problems
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• A critical point for random graphs with a given degree sequence
• Component structure of the vacant set induced by a random walk on a random graph
• Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time
• The Cover Time of Random Regular Graphs
• Greedy Random Walk