Geodesic
Combinatorial Markov chains on linear extensions
Journal of Algebraic Combinatorics, Tome 39 (2014) no. 4, pp. 853-881.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

We consider generalizations of Schützenberger's promotion operator on the set $\mathcal{L}$ of linear extensions of a finite poset of size $n$. This gives rise to a strongly connected graph on $\mathcal{L}$. By assigning weights to the edges of the graph in two different ways, we study two Markov chains, both of which are irreducible. The stationary state of one gives rise to the uniform distribution, whereas the weights of the stationary state of the other have a nice product formula. This generalizes results by Hendricks on the Tsetlin library, which corresponds to the case when the poset is the anti-chain and hence $\mathcal{L}=S_n$ is the full symmetric group. We also provide explicit eigenvalues of the transition matrix in general when the poset is a rooted forest. This is shown by proving that the associated monoid is $\mathcal{R}$-trivial and then using Steinberg's extension of Brown's theory for Markov chains on left regular bands to $\mathcal {R}$-trivial monoids.
Classification : 05C40, 60J10, 05C81, 06A07, 20B30
Keywords: linear extensions, posets, promotion operator, Markov chains 
@article{JAC_2014__39_4_a5,
     author = {Ayyer, Arvind and Klee, Steven and Schilling, Anne},
     title = {Combinatorial {Markov} chains on linear extensions},
     journal = {Journal of Algebraic Combinatorics},
     pages = {853--881},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2014__39_4_a5/}
}
TY  - JOUR
AU  - Ayyer, Arvind
AU  - Klee, Steven
AU  - Schilling, Anne
TI  - Combinatorial Markov chains on linear extensions
JO  - Journal of Algebraic Combinatorics
PY  - 2014
SP  - 853
EP  - 881
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2014__39_4_a5/
LA  - en
ID  - JAC_2014__39_4_a5
ER  - 
%0 Journal Article
%A Ayyer, Arvind
%A Klee, Steven
%A Schilling, Anne
%T Combinatorial Markov chains on linear extensions
%J Journal of Algebraic Combinatorics
%D 2014
%P 853-881
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2014__39_4_a5/
%G en
%F JAC_2014__39_4_a5
Ayyer, Arvind; Klee, Steven; Schilling, Anne. Combinatorial Markov chains on linear extensions. Journal of Algebraic Combinatorics, Tome 39 (2014) no. 4, pp. 853-881. http://geodesic.mathdoc.fr/item/JAC_2014__39_4_a5/