Cutoff phenomenon for random walks on Kneser graphs

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 the 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 the 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 boolean AND B = empty set. We show that for any k = O(n), the random walk on K(2n + k, n) exhibits a cutoff at 1/2log(1+k/n) (2n + k) with a window of size O(n/k) (C) 2014 Elsevier B.V. All rights reserved.