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.

KEYWORDS:

• sampling linear extensions
• posets
• random-to-random shuffling
• discrete Markov chain
• spectral gap
• second largest eigenvalue
• mixing time

2010 AMS Subject Classification:

• 60J10
• 05C81
• 06A07

Acknowledgments

We would like to thank Franco Saliola and Mike Zabrocki for helpful discussions. Many thanks to Peter Gibson for suggesting the use of Wilkinson’s theorem [Wilkinson 65, Dancis and Davis 87] to prove the conjecture, and Vincent Delecroix for helpful comments on the manuscript.

The authors would like to thank the Indian Institute for Science in Bangalore for hospitality, where part of this work was done.

Funding

AS and NT were partially supported by DSTO/PAM/GR/1171 from the National Mathematics Institute for their trip to Bangalore. AS was partially supported by NSF grant OCI–1147247 and the VI–MSS program sponsored by ICERM. NT was partially supported by NSF grant OCI–1147247 for his visit to UC Davis, where part of this work was performed. AA would like to acknowledge support in part by a UGC Centre for Advanced Study grant.