Cutoff for random lifts of weighted graphs

DOI10.1214/21-AOP1534zbMath1486.05284arXiv1908.02898OpenAlexW4213443164MaRDI QIDQ2119212

Guillaume Conchon-Kerjan

Publication date: 23 March 2022

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

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

zbMATH Keywords

cutoffrandom walksperiodic trees

Mathematics Subject Classification ID

Trees (05C05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Signed and weighted graphs (05C22) Random walks on graphs (05C81) Expander graphs (05C48)

Related Items (2)

CUTOFF AT THE ENTROPIC TIME FOR RANDOM WALKS ON COVERED EXPANDER GRAPHS ⋮ Using Bernoulli maps to accelerate mixing of a random walk on the torus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotic entropy of random walks on regular languages over a finite alphabet
• Cutoff on all Ramanujan graphs
• Spectra of lifted Ramanujan graphs
• Random walks and percolation on trees
• Cutoff phenomena for random walks on random regular graphs
• The rate of escape for anisotropic random walks in a tree
• Random walk on periodic trees
• Relative expanders or weakly relatively Ramanujan graphs.
• Random walks on trees with finitely many cone types
• Random walks on the random graph
• A simple criterion for transience of a reversible Markov chain
• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Random walks on dynamic configuration models: a trichotomy
• Eigenvalues of random lifts and polynomials of random permutation matrices
• A Dirichlet principle for non reversible Markov chains and some recurrence theorems
• Random lifts of graphs: perfect matchings
• Rate of Escape of Random Walks on Regular Languages and Free Products by Amalgamation of Finite Groups
• Random walks and periodic continued fractions
• Minors in lifts of graphs
• Expander graphs and their applications
• Mathematical Aspects of Mixing Times in Markov Chains
• Shuffling Cards and Stopping Times
• Better expanders and superconcentrators
• Generating a random permutation with random transpositions
• Random lifts of graphs: Independence and chromatic number
• Comparing mixing times on sparse random graphs
• Random Lifts of Graphs: Edge Expansion

This page was built for publication: Cutoff for random lifts of weighted graphs