Cutoff Phenomenon for Random Walks on Kneser Graphs

2014/04/17 by Ali Pourmiri, Pourmiri, Ali, Thomas Sauerwald +1
Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Markov Chains and Monte Carlo Methods #Probability (math.PR) #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1404.4598

openalex publication_date 2014/04/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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,…,2n+k\ of size n and two vertices A and B being connected by an edge if A∩ B =∅. We show that for any k=O(n), the random walk on K(2n+k,n) exhibits a cutoff at (1)/(2)log_1+k/n(2n+k) with a window of size O((n)/(k)).

Related

• Cutoff for non-backtracking random walks on sparse random graphs
• Explicit expanders with cutoff phenomena
• Random walk on sparse random digraphs
• Cutoff for random walks on graphs with bottlenecks
• The Cut-Off Phenomenon in Random Walks on Finite Groups