Spectral gap for random-to-random shuffling on linear extensions

Abstract

In this article, we propose a new Markov chain which generalizes random-to-random shuffling on permutations to random-to-random shuffling on linear extensions of a finite poset of size n. We conjecture that the second largest eigenvalue of the transition matrix is bounded above by (1 + 1/n)(1 − 2/n) with equality when the poset is disconnected. This Markov chain provides a way to sample the linear extensions of the poset with a relaxation time bounded above by n²/(n + 2) and a mixing time of O(n²log n). We conjecture that the mixing time is in fact O(nlog n) as for the usual random-to-random shuffling.