Cutoff phenomenon for random walks on Kneser graphs

DOI10.1016/J.DAM.2014.04.015zbMATH Open1297.05224arXiv1404.4598OpenAlexW1985002718MaRDI QIDQ403570FDOQ403570

Authors: Ali Pourmiri, Thomas Sauerwald 

Publication date: 29 August 2014

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

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)$.

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

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

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)

Cites Work

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

Cited In (3)

• On mixing of certain random walks, cutoff phenomenon and sharp threshold of random matroid processes
• Cutoff phenomenon for the simple exclusion process on the complete graph
• 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)