Markov Chains for Promotion Operators
From MaRDI portal
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.
Recommendations
- Properties of the promotion Markov chain on linear extensions
- Promotion patterns: Markov chain theory -- semi Markov theory
- Markov Chains
- Markov Chains
- About Markovian operators
- Frobenius-Perron operator description of Markov chains
- Markov chains. Theory and applications
- scientific article; zbMATH DE number 5875157
- scientific article; zbMATH DE number 4018043
Cites work
- A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
- A recurrence for linear extensions
- Affine type A crystal structure on tensor products of rectangles, Demazure characters, and nilpotent varieties
- An exact formula for the move-to-front rule for self-organizing lists
- An extension of a theorem concerning an interesting Markov chain
- Chaînes de Markov sur les permutations
- Combinatorial Markov chains on linear extensions
- Cyclic sieving, promotion, and representation theory
- Directed nonabelian sandpile models on trees
- Dual equivalence with applications, including a conjecture of Proctor
- Evacuation of labelled graphs
- FINITE AUTOMATA AND MODELS OF SIMPLE FORMS OF BEHAVIOUR
- Functions of random walks on hyperplane arrangements
- scientific article; zbMATH DE number 3678815 (Why is no real title available?)
- scientific article; zbMATH DE number 1033382 (Why is no real title available?)
- scientific article; zbMATH DE number 2070260 (Why is no real title available?)
- Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
- Möbius functions and semigroup representation theory.
- Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
- Note: random-to-front shuffles on trees
- On the matrix occurring in a linear search problem
- On the structure of semigroups
- Promotion and evacuation
- Promotion des morphismes d'ensembles ordonnes
- Random walks and hyperplane arrangements
- Random Walks, Arrangements, Cell Complexes, Greedoids, and Self-Organizing Libraries
- Semigroups, rings, and Markov chains
- Stochastic rearrangement rules for self-organizing data structures
- The heaps process, libraries, and size-biased permutations
- The stationary distribution of an interesting Markov chain
Cited in
(12)- Promotion and evacuation
- Unified theory for finite Markov chains
- Random walks on rings and modules
- The Tamari block lattice: an order on saturated chains in the Tamari lattice
- Combinatorial Markov chains on linear extensions
- Character theory of monoids over an arbitrary field.
- Markov chains on graded posets. Compatibility of up-directed and down-directed transition probabilities
- Mixing time for Markov chain on linear extensions
- Toric promotion
- Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
- Random shuffles on trees using extended promotion
- Properties of the promotion Markov chain on linear extensions
This page was built for publication: Markov Chains for Promotion Operators
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5112365)
