A random walk on the Rado graph

DOI10.1007/978-3-031-13851-5_13arXiv2205.06894OpenAlexW4313342017MaRDI QIDQ6203570FDOQ6203570

Sourav Chatterjee, Persi Diaconis, Laurent Miclo

Publication date: 5 April 2024

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

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^{*}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.

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)

Cites Work

• Random Walks on Infinite Graphs and Groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• Bounds for the Probability of a Union, with Applications
• An upper bound for the probability of a union
• The random graph
• Relations between isoperimetry and spectral gap for finite Markov chains
• An improved Bonferroni inequality and applications
• Weighted Hardy and Poincaré Inequalities on Trees
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Random walks on the random graph
• Title not available (Why is that?)
• A survey of results on random random walks on finite groups
• The evolution of the mixing rate of a simple random walk on the giant component of a random graph
• Random Walks on Some Countable Groups
• Critical random graphs: Diameter and mixing time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random doubly stochastic tridiagonal matrices
• Percolation on an infinitely generated group
• Random walk on sparse random digraphs
• Hardy's inequality and its descendants: a probability approach
• Complexity and randomness in the Heisenberg groups (and beyond)
• Locally infinite graphs and symmetries

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)