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

UC Davis

UC Davis Previously Published Works bannerUC Davis

Markov Chains for Promotion Operators

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

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