Random walks on the random graph

DOI10.1214/17-AOP1189zbMath1393.60077arXiv1504.01999MaRDI QIDQ1747756

Allan Sly, Yuval Peres, Nathanaël Berestycki, Eyal Lubetzky

Publication date: 27 April 2018

Published in: The Annals of Probability (Search for Journal in Brave)

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

zbMATH Keywords

random walkmixing timerandom graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 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, An entropic proof of cutoff on Ramanujan graphs, Invariant measures, Hausdorff dimension and dimension drop of some harmonic measures on Galton-Watson trees, A threshold for cutoff in two-community random graphs, Random walk on sparse random digraphs, CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS, Mixing time of PageRank surfers on sparse random digraphs, Voter models on subcritical scale‐free random graphs, A central limit theorem for the mean starting hitting time for a random walk on a random graph, 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 for permuted Markov chains, Rankings in directed configuration models with heavy tailed in-degrees, A random walk on the Rado graph, The degree-wise effect of a second step for a random walk on a graph, Unnamed Item, Cutoff at the ``entropic time for sparse Markov chains, Queues on a dynamically evolving graph, Random walks on dynamic configuration models: a trichotomy, Cutoff for random walk on dynamical Erdős-Rényi graph, Mixing time trichotomy in regenerating dynamic digraphs, Reversibility of the non-backtracking random walk, Comparing mixing times on sparse random graphs, Harmonic measure for biased random walk in a supercritical Galton-Watson tree, Linking the mixing times of random walks on static and dynamic random graphs, Expansion in supercritical random subgraphs of the hypercube and its consequences

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Mixing time of near-critical random graphs
• Faster mixing and small bottlenecks
• Critical random graphs: Diameter and mixing time
• Cutoff phenomena for random walks on random regular graphs
• Limiting behavior for the distance of a random walk
• Large deviations for random walks on Galton-Watson trees: Averaging and uncertainty
• Biased random walks on Galton-Watson trees
• Cutoff for nonbacktracking random walks on sparse random graphs
• Anatomy of the giant component: the strictly supercritical regime
• Faster mixing via average conductance
• The mixing time of the giant component of a random graph
• Anatomy of a young giant component in the random graph
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• RANDOM ELECTRICAL NETWORKS ON COMPLETE GRAPHS
• The Evolution of Random Graphs
• Component behavior near the critical point of the random graph process
• Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measure
• The Diameter of Sparse Random Graphs
• The total progeny in a branching process and a related random walk