A random walk on the Rado graph

DOI10.1007/978-3-031-13851-5_13MaRDI QIDQ6203570OpenAlexFDO

Authors Sourav Chatterjee, Persi Diaconis, Laurent Miclo

Publication date 5 April 2024

Published in Toeplitz Operators and Random Matrices (Search for Journal in Brave)

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

zbMATH Keywords

random walkrandom graphHardy's inequalityRado graphCheeger's inequalitymixing speed

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Ergodicity, mixing, rates of mixing (37A25) Infinite graphs (05C63) Random walks on graphs (05C81) Continuous-time Markov processes on discrete state spaces (60J27) Sobolev (and similar kinds of) spaces of functions of discrete variables (46E39)

Abstract: The Rado graph, also known as the random graph $G(infty,p)$, is a classical limit object for finite graphs. We study natural ball walks as a way of understanding the geometry of this graph. For the walk started at $i$, we show that order $lo{g}_2^{\ast }i$ steps are sufficient, and for infinitely many $i$, necessary for convergence to stationarity. The proof involves an application of Hardy's inequality for trees.

Recommendations

• scientific article; zbMATH DE number 1944718
• scientific article; zbMATH DE number 3893250
• scientific article; zbMATH DE number 909704
• A preferential attachment process approaching the Rado graph
• scientific article; zbMATH DE number 2128200

Cites work

• scientific article; zbMATH DE number 1687029 (Why is no real title available?)
• scientific article; zbMATH DE number 1069282 (Why is no real title available?)
• scientific article; zbMATH DE number 1944718 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• A survey of results on random random walks on finite groups
• An improved Bonferroni inequality and applications
• An upper bound for the probability of a union
• Bounds for the Probability of a Union, with Applications
• Complexity and randomness in the Heisenberg groups (and beyond)
• Critical random graphs: Diameter and mixing time
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Hardy's inequality and its descendants: a probability approach
• Locally infinite graphs and symmetries
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Percolation on an infinitely generated group
• Random Walks on Infinite Graphs and Groups
• Random doubly stochastic tridiagonal matrices
• Random walk on sparse random digraphs
• Random walks on some countable groups
• Random walks on the random graph
• Relations between isoperimetry and spectral gap for finite Markov chains
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• The random graph
• Weighted Hardy and Poincaré Inequalities on Trees

This page was built for publication: A random walk on the Rado graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6203570)