Markov Chains for Promotion Operators
Skip to main content
Open Access Publications from the University of California

Markov Chains for Promotion Operators

  • Author(s): Ayyer, Arvind
  • Klee, Steven
  • Schilling, Anne
  • et al.

We consider generalizations of Schuetzenberger's promotion operator on the set L of linear extensions of a finite poset. This gives rise to a strongly connected graph on L. In earlier work (arXiv:1205.7074), we studied promotion-based Markov chains on these linear extensions which generalizes results on the Tsetlin library. We used the theory of R-trivial monoids in an essential way to obtain explicitly the eigenvalues of the transition matrix in general when the poset is a rooted forest. We first survey these results and then present explicit bounds on the mixing time and conjecture eigenvalue formulas for more general posets. We also present a generalization of promotion to arbitrary subsets of the symmetric group.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View