Cutoff for random walk on dynamical Erdős-Rényi graph

DOI10.1214/20-AIHP1057zbMath1465.05168arXiv1807.04719OpenAlexW3027537609MaRDI QIDQ2028956

Sam Thomas, Perla Sousi

Publication date: 3 June 2021

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

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

zbMATH Keywords

random walkcouplingdynamical percolationmixing timesErdős-Rényi

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37) Continuous-time Markov processes on discrete state spaces (60J27) Random walks on graphs (05C81)

Related Items

Cutoff for random lifts of weighted graphs ⋮ Random Walks on Randomly Evolving Graphs ⋮ Mixing time trichotomy in regenerating dynamic digraphs ⋮ Linking the mixing times of random walks on static and dynamic random graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Cover time of a random graph with given degree sequence
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Faster mixing and small bottlenecks
• Approximate counting, uniform generation and rapidly mixing Markov chains
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Dynamical percolation
• Mixing times of random walks on dynamic configuration models
• Random walks on the random graph
• Sudden emergence of a giant \(k\)-core in a random graph
• Mixing time for random walk on supercritical dynamical percolation
• Anatomy of the giant component: the strictly supercritical regime
• Random Graphs and Complex Networks
• The mixing time of the giant component of a random graph
• Introduction to Random Graphs
• Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
• Approximating the Permanent
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• A Chernoff Bound for Random Walks on Expander Graphs
• On the Method of Typical Bounded Differences