Cutoff phenomenon for random walks on Kneser graphs

DOI10.1016/J.DAM.2014.04.015MaRDI QIDQ403570zbMATHOpenAlexFDO

Authors Ali Pourmiri, Thomas Sauerwald

Publication date 29 August 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Markov chainrandom walkKneser graphcutoff phenomenon

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Abstract: The cutoff phenomenon for an ergodic Markov chain describes a sharp transition in the convergence to its stationary distribution, over a negligible period of time, known as cutoff window. We study the cutoff phenomenon for simple random walks on Kneser graphs, which is a family of ergodic Markov chains. Given two integers $n$ and $k$, the Kneser graph $K(2n+k,n)$ is defined as the graph with vertex set being all subsets of $1,ldots,2n+k$ of size $n$ and two vertices $A$ and $B$ being connected by an edge if $AcapB=emptyset$. We show that for any $k=O(n)$, the random walk on $K(2n+k,n)$ exhibits a cutoff at $frac12lo{g}_{1+k/n}(2n+k)$ with a window of size $O(fracnk)$.

Recommendations

• Cutoff for nonbacktracking random walks on sparse random graphs
• Cutoff phenomena for random walks on random regular graphs
• Explicit expanders with cutoff phenomena
• The cut-off phenomenon for random walks on Hamming graphs with variable growth conditions
• Phénomène de cutoff pour certaines marches aléatoires sur le groupe symétrique

Cites work

• scientific article; zbMATH DE number 1600999 (Why is no real title available?)
• scientific article; zbMATH DE number 2128202 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Cutoff phenomena for random walks on random regular graphs
• Enumeration and random walks on finite groups
• Explicit expanders with cutoff phenomena
• Generating a random permutation with random transpositions
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Mixing times of lozenge tiling and card shuffling Markov chains
• More odd graph theory
• Rates of convergence of random walk on distance regular graphs
• Shuffling Cards and Stopping Times
• The cutoff phenomenon for ergodic Markov processes
• The cutoff phenomenon for randomized riffle shuffles
• The cutoff phenomenon in finite Markov chains.
• Time to Reach Stationarity in the Bernoulli–Laplace Diffusion Model

Cited in

(3)

• Cutoff phenomenon for the simple exclusion process on the complete graph
• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
• Cutoff for a stratified random walk on the hypercube

This page was built for publication: Cutoff phenomenon for random walks on Kneser graphs

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