Cutoff phenomena for random walks on random regular graphs

DOI10.1215/00127094-2010-029zbMath1202.60012arXiv0812.0060OpenAlexW2033635202WikidataQ105584385 ScholiaQ105584385MaRDI QIDQ984454

Eyal Lubetzky, Allan Sly

Publication date: 19 July 2010

Published in: Duke Mathematical Journal (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Sums of independent random variables; random walks (60G50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Convergence of probability measures (60B10) Random walks on graphs (05C81)

Related Items

A phase transition for repeated averages, Universality of cutoff for graphs with an added random matching, Cutoff for random lifts of weighted graphs, Complex networks: structure and functionality, Mixing times of random walks on dynamic configuration models, Spectral gap in random bipartite biregular graphs and applications, No cutoff for circulants: an elementary proof, No cutoff in spherically symmetric trees, Cutoff on all Ramanujan graphs, Cutoff on Ramanujan complexes and classical groups, A threshold for cutoff in two-community random graphs, Critical value asymptotics for the contact process on random graphs, Random walk on sparse random digraphs, Cut-off phenomenon for Ornstein-Uhlenbeck processes driven by Lévy processes, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, Simple random walk on long range percolation clusters. I: Heat kernel bounds, Cutoff phenomenon for random walks on Kneser graphs, Mixing time of PageRank surfers on sparse random digraphs, Local Kesten-McKay law for random regular graphs, Speeding up random walk mixing by starting from a uniform vertex, Large scale stochastic dynamics. Abstracts from the workshop held September 11--17, 2022, Scale-free percolation mixing time, Cutoff profile of the metropolis biased card shuffling, Cutoff for permuted Markov chains, Finite-size scaling, phase coexistence, and algorithms for the random cluster model on random graphs, Cutoff for the Ising model on the lattice, Rankings in directed configuration models with heavy tailed in-degrees, Giant vacant component left by a random walk in a random \(d\)-regular graph, Simple versus nonsimple loops on random regular graphs, The power of averaging at two consecutive time steps: proof of a mixing conjecture by Aldous and Fill, On Active and Passive Testing, The degree-wise effect of a second step for a random walk on a graph, Speeding up Markov chains with deterministic jumps, Random walks on Ramanujan complexes and digraphs, Cutoff at the ``entropic time for sparse Markov chains, Survival and extinction of epidemics on random graphs with general degree, Random walks on the random graph, Cutoff for General Spin Systems with Arbitrary Boundary Conditions, Spectra of lifted Ramanujan graphs, Some spectral properties of the non-backtracking matrix of a graph, Level-set percolation of the Gaussian free field on regular graphs II: finite expanders, Mixing time trichotomy in regenerating dynamic digraphs, An exposition to information percolation for the Ising model, Information percolation and cutoff for the stochastic Ising model, The spectral gap of sparse random digraphs, Deterministic walks with choice, Correction to: ``Speeding up Markov chains with deterministic jumps, Comparing mixing times on sparse random graphs, Contact process on a graph with communities, Random doubly stochastic tridiagonal matrices, Linking the mixing times of random walks on static and dynamic random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Total variation cutoff in birth-and-death chains
• The cutoff phenomenon for ergodic Markov processes
• Limiting behavior for the distance of a random walk
• Minimization algorithms and random walk on the d-cube
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Generating random elements in \(SL_ n(F_ q)\) by random transvections
• On the complexity of an optimal non-blocking commutation scheme without reorganization
• Recursive construction for 3-regular expanders
• Entropy waves, the zig-zag graph product, and new constant-degree expanders
• NON-BACKTRACKING RANDOM WALKS MIX FASTER
• A proof of Alon’s second eigenvalue conjecture and related problems
• Shuffling Cards and Stopping Times
• Generating a random permutation with random transpositions
• The cutoff phenomenon in finite Markov chains.
• The non-backtracking spectrum of the universal cover of a graph