Name
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(2)/(n + 2) and a mixing time of O(n(2)logn). We conjecture that the mixing time is in fact O(nlogn) as for the usual random-to-random shuffling. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1080/10586458.2015.1107868 | EXPERIMENTAL MATHEMATICS |
Keywords | Field | DocType |
sampling linear extensions,posets,random-to-random shuffling,discrete Markov chain,spectral gap,second largest eigenvalue,mixing time,60J10,05C81,06A07 | Mathematical analysis,Bounded set,Shuffling,Eigenvalues and eigenvectors,Topology,Discrete mathematics,Combinatorics,Stochastic matrix,Permutation,Markov chain,Spectral gap,Partially ordered set,Mathematics | Journal |
Volume | Issue | ISSN |
26.0 | 1.0 | 1058-6458 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Arvind Ayyer | 1 | 21 | 5.51 |
| Anne Schilling | 2 | 17 | 6.74 |
| Nicolas M. Thiéry | 3 | 12 | 4.66 |