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 nn and kk, the Kneser graph K(2n+k,n)K(2n+k,n) is defined as the graph with the vertex set being all subsets of {1,…,2n+k}{1,…,2n+k} of size nn and two vertices AA and BB being connected by an edge if A∩B=0̸A∩B=0̸. We show that for any k=O(n)k=O(n), the random walk on K(2n+k,n)K(2n+k,n) exhibits a cutoff at 12log1+k/n(2n+k) with a window of size O(nk).