1 Introduction

Schützenberger [30] introduced the notion of evacuation and promotion on the set of linear extensions of a finite poset P of size n. This generalizes promotion on standard Young tableaux defined in terms of jeu-de-taquin moves. Haiman [19] as well as Malvenuto and Reutenauer [26] simplified Schützenberger’s approach by expressing the promotion operator ∂ in terms of more fundamental operators τ i (1≤i<n), which either act as the identity or as a simple transposition. A beautiful survey on this subject was written by Stanley [33].

In this paper, we consider a slight generalization of the promotion operator defined as ∂ i =τ i τ i+1⋯τ n−1 for 1≤i≤n with ∂ 1=∂ being the original promotion operator. Since the operators ∂ i act on the set of all linear extensions of P, denoted \(\mathcal{L}(P)\), this gives rise to a graph whose vertices are the linear extensions and edges are labeled by the action of ∂ i . We show that this graph is strongly connected (see Proposition 4.1). As a result we obtain two irreducible Markov chains on \(\mathcal{L}(P)\) by assigning weights to the edges in two different ways. In one case, the stationary state is uniform, that is, every linear extension is equally likely to occur (see Theorem 4.3). In the other case, we obtain a nice product formula for the weights of the stationary distribution (see Theorem 4.5). We also consider analogous Markov chains for the adjacent transposition operators τ i , and give a combinatorial formula for their stationary distributions (see Theorems 4.4 and 4.7).

Our results can be viewed as a natural generalization of the results of Hendricks [20, 21] on the Tsetlin library [36], which is a model for the way an arrangement of books in a library shelf evolves over time. It is a Markov chain on permutations, where the entry in the ith position is moved to the front (or back depending on the conventions) with probability p i . Hendricks’ results from our viewpoint correspond to the case when P is an anti-chain and hence \(\mathcal{L}(P)=S_{n}\) is the full symmetric group. Many variants of the Tsetlin library have been studied and there is a wealth of literature on the subject. We refer the interested reader to the monographs by Letac [24] and by Dies [14], as well as the comprehensive bibliographies in [17] and [6].

One of the most interesting properties of the Tsetlin library Markov chain is that the eigenvalues of the transition matrix can be computed exactly. The exact form of the eigenvalues was independently investigated by several groups. Notably Donnelly [15], Kapoor and Reingold [23], and Phatarfod [27] studied the approach to stationarity in great detail. There has been some interest in finding exact formulas for the eigenvalues for generalizations of the Tsetlin library. The first major achievement in this direction was to interpret these results in the context of hyperplane arrangements [4, 6, 7]. This was further generalized to a class of monoids called left regular bands [10] and subsequently to all bands [11] by Brown. This theory has been used effectively by Björner [8, 9] to extend eigenvalue formulas on the Tsetlin library from a single shelf to hierarchies of libraries.

In this paper, we give explicit combinatorial formulas for the eigenvalues and multiplicities for the transition matrix of the promotion Markov chain when the underlying poset is a rooted forest (see Theorem 5.2). This is achieved by proving that the associated monoid is \(\mathcal {R}\)-trivial and then using a generalization of Brown’s theory [10] of Markov chains for left regular bands to the \(\mathcal {R}\)-trivial case using results by Steinberg [34, 35].

Computing the number of linear extensions is an important problem for real world applications [22]. For example, it relates to sorting algorithms in computer science, rankings in the social sciences, and efficiently counting standard Young tableaux in combinatorics. A recursive formula was given in [16]. Brightwell and Winkler [12] showed that counting the number of linear extensions is #P-complete. Bubley and Dyer [5] provided an algorithm to (almost) uniformly sample the set of linear extensions of a finite poset quickly. We propose new Markov chains for sampling linear extensions uniformly randomly. Further details are discussed in Sect. 7.

The paper is outlined as follows. In Sect. 2, we define the extended promotion operator and investigate some of its properties. The extended promotion and transposition operators are used in Sect. 3 to define various Markov chains, whose properties are studied in Sect. 4. We also prove formulas for the stationary distributions and explain the connection with the Tsetlin library there. In Sect. 5, we derive the partition function for the promotion Markov chains for rooted forests as well as all eigenvalues together with their multiplicities of the transition matrix. The statements about eigenvalues and multiplicities are proven in Sect. 6 using the theory of \(\mathcal {R}\)-trivial monoids. We end with possible directions for future research in Sect. 7. In the Appendix, we provide details about implementations of linear extensions, Markov chains, and their properties in Sage [28, 29] and Maple.

2 Extended promotion on linear extensions

2.1 Definition of extended promotion

Let P be an arbitrary poset of size n, with partial order denoted by ⪯. We assume that the elements of P are labeled by integers in [n]:={1,2,…,n}. In addition, we assume that the poset is naturally labeled, that is, if i,j∈P with i⪯j in P then i≤j as integers. Let \({\mathcal{L}}:={\mathcal{L}}(P)\) be the set of its linear extensions,

$$ {\mathcal{L}}(P) = \bigl\{ \pi\in S_{n} \mid i \prec j \text{ in }P \implies \pi^{-1}_{i} < \pi^{-1}_{j} \text{ as integers} \bigr\}, $$
(2.1)

which is naturally interpreted as a subset of the symmetric group S n . Note that the identity permutation e always belongs to \({\mathcal{L}}\). Let P j be the natural (induced) subposet of P consisting of elements k such that j⪯k [32].

We now briefly recall the idea of promotion of a linear extension of a poset P. Start with a linear extension \(\pi\in{ \mathcal{L}}(P)\) and imagine placing the label \(\pi^{-1}_{i}\) in P at the location i. By the definition of the linear extension, the labels will be well-ordered. The action of promotion of π will give another linear extension of P as follows:

  1. (i)

    The process starts with a seed, the label 1. First remove it and replace it by the minimum of all the labels covering it, i, say.

  2. (ii)

    Now look for the minimum of all labels covering i in the original poset, and replace it, and continue in this way.

  3. (iii)

    This process ends when a label is a “local maximum.” Place the label n+1 at that point.

  4. (iv)

    Decrease all the labels by 1.

This new linear extension is denoted π∂ [33].

Example 2.1

Figure 1 shows a poset (left) to which we assign the identity linear extension π=123456789. The linear extension π′=π∂=214537869 obtained by applying the promotion operator is depicted on the right. Note that indeed we place \(\pi_{i}^{'-1}\) in position i, namely 3 is in position 5 in π′, so that 5 in π∂ is where 3 was originally.

Fig. 1
figure 1

A linear extension π (left) and π∂ (right)

Full size image

Figure 2 illustrates the steps used to construct the linear extension π∂ from the linear extension π from Fig. 1. The Appendix includes Sage implementation of this action.

Fig. 2
figure 2

Constructing π∂ from π

Full size image

We now generalize this to extended promotion, whose seed is any of the numbers 1,2,…,n. The algorithm is similar to the original one, and we describe it for seed j. Start with the subposet P j and perform steps 1–3 in a completely analogous fashion. Now decrease all the labels strictly larger than j by 1 in P (not only P j ). Clearly, this gives a new linear extension, which we denote π∂ j . Note that ∂ n is always the identity.

The extended promotion operator can be expressed in terms of more elementary operators τ i (1≤i<n) as shown in [19, 26, 33] and has explicitly been used to count linear extensions in [16]. Let \(\pi=\pi_{1} \cdots\pi_{n} \in{ \mathcal{L}}(P)\) be a linear extension of a finite poset P in one-line notation. Then

$$ \pi\tau_i = \begin{cases} \pi_1 \cdots\pi_{i-1} \pi_{i+1} \pi_i \cdots\pi_n & \text{if }\pi_i\mbox{ and }\pi_{i+1}\mbox{ are not}\\ & \text{comparable in } P,\\ \pi_1 \cdots\pi_n & \text{otherwise.} \end{cases} $$
(2.2)

Alternatively, τ i acts non-trivially on a linear extension if interchanging entries π i and π i+1 yields another linear extension. Then as an operator on \({\mathcal{L}}(P)\),

$$ \partial_j = \tau_j \tau_{j+1} \cdots\tau_{n-1}. $$
(2.3)

2.2 Properties of τ i and extended promotion

The operators τ i are involutions (\(\tau_{i}^{2} = 1\)) and partially commute (τ i τ j =τ j τ i when |i−j|>1). Unlike the generators for the symmetric group, the τ i do not always satisfy the braid relation τ i τ i+1 τ i =τ i+1 τ i τ i+1. They do, however, satisfy (τ i τ i+1)6=1 [33].

Proposition 2.2

Let P be a poset on [n]. The braid relations

$$\pi\tau_j\tau_{j+1}\tau_j = \pi \tau_{j+1}\tau_j\tau_{j+1} $$

hold for all 1≤j<n−1 and all \(\pi\in{ \mathcal{L}}(P)\) if and only if P is a union of disjoint chains.

The proof is an easy case-by-case check. Since we do not use this result, we omit the proof.

It will also be useful to express the operators τ i in terms of the generalized promotion operator.

Lemma 2.3

For all 1≤j≤n−1, each operator τ j can be expressed as a product of promotion operators.

Proof

We prove the claim by induction on j, starting with the case that j=n−1 and decreasing until we reach the case that j=1. When j=n−1, the claim is obvious since τ n−1=∂ n−1. For j<n−1, we observe that

$$\begin{aligned} \tau_j =& \tau_{j}\tau_{j+1}\cdots \tau_{n-1} \tau_{n-1}\cdots \tau_{j+2} \tau_{j+1} \\ =& \partial_j \tau_{n-1} \cdots\tau_{j+2} \tau_{j+1}. \end{aligned}$$

By our inductive hypothesis, each of τ j+1,…,τ n−1 can be expressed as a product of promotion operators, and hence so too can τ j . □

3 Various Markov chains

We now consider various discrete-time Markov chains related to the extended promotion operator. For completeness, we briefly review the part of the theory relevant to us.

Fix a finite poset P of size n. The operators {τ i ∣1≤i<n} (resp., {∂ i ∣1≤i≤n}) define a directed graph on the set of linear extensions \({\mathcal{L}}(P)\). The vertices of the graph are the elements of \({\mathcal{L}}(P)\) and there is an edge from π to π′ if π′=πτ i (resp., π′=π∂ i ). We can now consider random walks on this graph with probabilities given formally by x 1,…,x n which sum to 1. In each case, we give two ways to assign the edge weights, see Sects. 3.1–3.4. An edge with weight x i is traversed with that rate. A priori, the x i ’s must be positive real numbers for this to make sense according to the standard techniques of Markov chains. However, the ideas work in much greater generality and one can think of this as an “analytic continuation.”

A discrete-time Markov chain is defined by the transition matrix M, whose entries are indexed by elements of the state space. In our case, they are labeled by elements of \({\mathcal{L}}(P)\). We take the convention that the (π′,π) entry gives the probability of going from π→π′. The special case of the diagonal entry at (π,π) gives the probability of a loop at the π. This ensures that column sums of M are one and consequently, one is an eigenvalue with row (left-) eigenvector being the all-ones vector. A Markov chain is said to be irreducible if the associated digraph is strongly connected. In addition, it is said to be aperiodic if the greatest common divisor of the lengths of all possible loops from any state to itself is one. For irreducible aperiodic chains, the Perron–Frobenius theorem guarantees that there is a unique stationary distribution. This is given by the entries of the column (right-) eigenvector of M with eigenvalue 1. Equivalently, the stationary distribution w(π) is the solution of the master equation, given by

$$ \sum_{\pi' \in{ \mathcal{L}}(P)} M_{\pi,\pi'} w \bigl(\pi'\bigr) = \sum_{\pi' \in{ \mathcal{L}}(P)} M_{\pi',\pi} w(\pi). $$
(3.1)

Edges which are loops contribute to both sides equally and thus cancel out. For more on the theory of finite state Markov chains, see [25].

We set up a running example that will be used for each case. The Appendix shows how to define and work with this poset in Sage.

Example 3.1

Define P by its covering relations {(1,3),(1,4),(2,3)}, so that its Hasse diagram is as shown below:

figure a

Then the elements of \({\mathcal{L}}(P) = \{ 1234, 1243, 1423, 2134, 2143 \} \) are represented by the following diagrams, respectively:

figure b

3.1 Uniform transposition graph

The vertices of the uniform transposition graph are the elements of \({\mathcal{L}}(P)\) and there is an edge between π and π′ if and only if π′=πτ j for some j∈[n], where we define τ n to be the identity map. This edge is assigned the symbolic weight x j . The name “uniform” is motivated by the fact that the stationary distribution of this Markov chain turns out to be uniform. Note that this chain is more general than the chains considered in [22] in that we assign arbitrary weights x j on the edges.

Example 3.2

Consider the poset and linear extensions of Example 3.1. The uniform transposition graph is illustrated in Fig. 3.

Fig. 3
figure 3

Uniform transposition graph for Example 3.1. Every vertex has four outgoing edges labeled x 1 to x 4 and self-loops are not drawn

Full size image

The transition matrix, with the lexicographically ordered basis, is given by

$$ \begin{pmatrix} x_{2}+x_{4} & x_{3} & 0 & x_{1} & 0 \\ x_{3} & x_{4} & x_{2} & 0 & x_{1} \\ 0 & x_{2} & x_{1}+x_{3}+x_{4} & 0 & 0 \\ x_{1} & 0 & 0 & x_{2}+x_{4} & x_{3} \\ 0 & x_{1} & 0 & x_{3} & x_{2}+x_{4} \end{pmatrix}. $$

Note that the weight x 4 only appears on the diagonal since τ 4 acts as the identity for n=4. By construction, the column sums of the transition matrix are one. Note that in this example the row sums are also one (since the matrix is symmetric), which means that the stationary state of this Markov chain is uniform. We will prove this in general in Theorem 4.4.

3.2 Transposition graph

The transposition graph is defined in the same way as the uniform transposition graph, except that the edges are given the symbolic weight \(x_{\pi_{j}}\) whenever τ j takes π→π′.

Example 3.3

The transposition graph for the poset in Example 3.1 is illustrated in Fig. 4. The transition matrix is given by

$$ \begin{pmatrix} x_{2}+x_{4} & x_{4} & 0 & x_{2} & 0 \\ x_{3} & x_{3} & x_{4} & 0 & x_{2} \\ 0 & x_{2} & x_{1}+x_{2}+x_{3} & 0 & 0 \\ x_{1} & 0 & 0 & x_{1}+x_{4} & x_{4} \\ 0 & x_{1} & 0 & x_{3} & x_{1}+x_{3} \end{pmatrix} . $$
(3.2)

Again, by definition the column sums are one, but the row sums are not one in this example. In fact, the stationary distribution (column vector with eigenvalue 1) is given by the eigenvector

$$ \begin{pmatrix} 1, & \displaystyle{\frac{x_{{3}}}{x_{{4}}}}, & \displaystyle{\frac{x_{{2}}x_{{3}}}{{x_{{4}}}^{2}}}, & \displaystyle{\frac{x_{{1}}}{x_{{2}}}}, & \displaystyle{\frac{x_{{1}}x_{{3}}}{x_{{2}}x_{{4}}}} \end{pmatrix} ^{T} . $$
(3.3)

We give a closed form expression for the weights of the stationary distribution in the general case in Theorem 4.7.

Fig. 4
figure 4

Transposition graph for Example 3.1. Every vertex has four outgoing edges labeled x 1 to x 4 and self-loops are not drawn

Full size image

3.3 Uniform promotion graph

The vertices of the uniform promotion graph are labeled by elements of \({\mathcal{L}}(P)\) and there is an edge between π and π′ if and only if π′=π∂ j for some j∈[n]. In this case, the edge is given the symbolic weight x j .

Example 3.4

The uniform promotion graph for the poset in Example 3.1 is illustrated in Fig. 5. The transition matrix, with the lexicographically ordered basis, is given by

$$ \begin{pmatrix} x_{4} & x_{3} & x_{1}+x_{2} & 0 & 0 \\ x_{2}+x_{3} & x_{4} & 0 & x_{1} & 0 \\ 0 & x_{2} & x_{3}+x_{4} & 0 & x_{1} \\ 0 & x_{1} & 0 & x_{4} & x_{2}+x_{3} \\ x_{1} & 0 & 0 & x_{2} + x_{3} & x_{4} \end{pmatrix} . $$

Note that as in Example 3.2 the row sums are one although the matrix is not symmetric, so that the stationary state of this Markov chain is uniform. We prove this for general finite posets in Theorem 4.3.

Fig. 5
figure 5

Uniform promotion graph for Example 3.1. Every vertex has four outgoing edges labeled x 1 to x 4 and self-loops are not drawn

Full size image

As in the uniform transposition graph, x 4 occurs only on the diagonal in the above transition matrix. This is because the action of ∂ 4 (or in general ∂ n ) maps every linear extension to itself resulting in a loop.

3.4 Promotion graph

The promotion graph is defined in the same fashion as the uniform promotion graph with the exception that the edge between π and π′ when π′=π∂ j is given the weight \(x_{\pi_{j}}\).

Example 3.5

The promotion graph for the poset of Example 3.1 is illustrated in Fig. 6. Although it might appear that there are many more edges here than in Fig. 5, this is not the case. The transition matrix this time is given by

$$ \begin{pmatrix} x_{4} & x_{4} & x_{1}+x_{4} & 0 & 0 \\ x_{2}+x_{3} & x_{3} & 0 & x_{2} & 0 \\ 0 & x_{2} & x_{2}+x_{3} & 0 & x_{2} \\ 0 & x_{1} & 0 & x_{4} & x_{1}+x_{4} \\ x_{1} & 0 & 0 & x_{1} + x_{3} & x_{3} \end{pmatrix} . $$

Notice that row sums are no longer one. The stationary distribution, as a vector written in row notation is

$$ \begin{pmatrix} 1, & \displaystyle\frac{x_{1}+x_{2}+x_{3}}{x_{1}+x_{2}+x_{4}}, & \displaystyle\frac{(x_{1}+x_{2})(x_{1}+x_{2}+x_{3})}{(x_{1}+x_{2})(x_{1}+x_{2}+x_{4})}, & \displaystyle\frac{x_{1}}{x_{2}}, & \displaystyle\frac{x_{1}(x_{1}+x_{2}+x_{3})}{x_{2}(x_{1}+x_{2}+x_{4})} \end{pmatrix} ^{T} . $$

Again, we will give a general such result in Theorem 4.5.

Fig. 6
figure 6

Promotion graph for Example 3.1. Every vertex has four outgoing edges labeled x 1 to x 4 and self-loops are not drawn

Full size image

In the Appendix, implementations of these Markov chains in Sage and Maple are discussed.

4 Properties of the various Markov chains

In Sect. 4.1, we prove that the Markov chains defined in Sect. 3 are all irreducible. This is used in Sect. 4.2 to conclude that their stationary state is unique and either uniform or given by an explicit product formula in their weights.

Throughout this section, we fix a poset P of size n and let \({\mathcal{L}}:={\mathcal{L}}(P)\) be the set of its linear extensions.

4.1 Irreducibility

We now show that the four graphs of Sect. 3 are all strongly connected.

Proposition 4.1

Consider the digraph G whose vertices are labeled by elements of \({\mathcal{L}}\) and whose edges are given as follows: for \(\pi, \pi' \in{ \mathcal{L}}\), there is an edge between π and π′ in G if and only if π′=π∂ j (resp., π′=πτ j ) for some j∈[n] (resp., j∈[n−1]). Then G is strongly connected.

Proof

We begin by showing the statement for the generalized promotion operators ∂ j . From an easy generalization of [33], we see that extended promotion, given by ∂ j , is a bijection for any j. Therefore, every element of \({\mathcal{L}}\) has exactly one such edge pointing in and one such edge pointing out. Moreover, ∂ j has finite order, so that \(\pi\partial_{j}^{k} = \pi\) for some k. In other words, the action of ∂ j splits \({\mathcal{L}}\) into disjoint cycles. In particular, π∂ n =π for all π so that it decomposes \({\mathcal{L}}\) into cycles of size 1.

It suffices to show that there is a directed path from any π to the identity e. We prove this by induction on n. The case of the poset with a single element is vacuous. Suppose the statement is true for every poset of size n−1. We have two cases. First, suppose \(\pi^{-1}_{1}=1\). In this case, ∂ 2,…,∂ n act on \({\mathcal{L}}\) in exactly the same way as ∂ 1,…,∂ n−1 on \({\mathcal{L}}'\), the set of linear extensions of P′, the poset obtained from P by removing 1. Then the directed path exists by the induction assumption.

Instead, suppose \(\pi^{-1}_{1}=j\) and \(\pi^{-1}_{k}=1\), for j,k>1. In other words, the label j is at position 1 and label 1 is at position k of P. Since j is at the position of a minimal element in P, it does not belong to the upper set of 1 (that is j⋡1 in the relabeled poset). Thus, the only effect on j of applying ∂ 1 is to reduce it by 1, i.e., if π′=π∂ 1, then \(\pi'^{-1}_{1}=j-1\). Continuing this way, we can get to the previous case by the action of \(\partial_{1}^{j-1}\) on π.

The statement for the τ j now follows from Lemma 2.3. □

Corollary 4.2

Assuming that the edge weights are strictly positive, all Markov chains of Sect. 3 are irreducible and their stationary distribution is unique.

Proof

Since the underlying graph of all four Markov chains of Sect. 3 is strongly connected, they are irreducible. The existence of a single loop at any vertex of the graph guarantees aperiodicity. The uniqueness of the stationary distribution then follows by standard theory of Markov chains [25, Chap. 1]. □

4.2 Stationary states

In this section, we prove properties of the stationary state of the various discrete-time Markov chains defined in Sect. 3, assuming that all x i ’s are strictly positive.

Theorem 4.3

The discrete-time Markov chain according to the uniform promotion graph has the uniform stationary distribution, that is, each linear extension is equally likely to occur.

Proof

Stanley showed [33] that the promotion operator has finite order, that is, ∂ k=id for some k. The same arguments go through for the extended promotion operators ∂ j . Therefore, at each vertex \(\pi\in{ \mathcal{L}}(P)\), there is an incoming and outgoing edge corresponding to ∂ j for each j∈[n]. For the uniform promotion graph, an edge for ∂ j is assigned weight x j , and hence the row sum of the transition matrix is one, which proves the result. Equivalently, the all ones vector is the required eigenvector. □

Theorem 4.4

The discrete-time Markov chain according to the uniform transposition graph has the uniform stationary distribution.

Proof

Since each τ j is an involution, every incoming edge with weight x j has an outgoing edge with the same weight. Another way of saying the same thing is that the transition matrix is symmetric. By definition, the transition matrix is constructed so that column sums are one. Therefore, row sums are also one. □

We now turn to the promotion and transposition graphs of Sect. 3. In this case, we find nice product formulas for the stationary weights.

Theorem 4.5

The stationary state weight w(π) of the linear extension \(\pi\in {\mathcal{L}}(P)\) for the discrete-time Markov chain for the promotion graph is given by

$$ w(\pi) = \prod_{i=1}^{n} \frac{x_{1}+ \cdots+ x_{i}}{ x_{\pi_1}+ \cdots+ x_{\pi_i}}, $$
(4.1)

assuming w(e)=1.

Remark 4.6

The entries of w do not, in general, sum to one. Therefore, this is not a true probability distribution, but this is easily remedied by a multiplicative constant Z P depending only on the poset P.

Proof of Theorem 4.5

We prove the theorem by induction on n. The case n=1 is trivial. By Remark 4.6, it suffices to prove the result for any normalization of w(π). For our purposes it is most convenient to use the normalization

$$ w(\pi) = \prod_{i=1}^{n} \frac{1}{x_{\pi_1}+ \cdots+ x_{\pi_i}}. $$
(4.2)

To prove (4.2), we need to show that it satisfies the master equation (3.1), rewritten as

$$ w(\pi) \Biggl(\sum_{i=1}^n x_{\pi_i} \Biggr) = \sum_{\substack{j=1 \\ \pi'=\pi\tau_{n-1} \cdots\tau_j}}^n x_{\pi'_j} w\bigl(\pi'\bigr). $$
(4.3)

The left-hand side is the contribution of the outgoing edges, whereas the right-hand side gives the weights of the incoming edges of vertex π.

Singling out the term j=n and setting \(\tilde{\pi} := \pi\tau _{n-1}\), the right-hand side of (4.3) becomes

$$ x_{\pi_n} w(\pi) + \sum_{\substack{j=1 \\ \pi' = \tilde{\pi} \tau_{n-2} \cdots\tau _j}}^{n-1} x_{\pi'_j} w\bigl(\pi'\bigr). $$
(4.4)

Now, notice that the nth entry of π′ in one-line notation in every term of the sum is \(\tilde{\pi}_{n}\) which is either π n or π n−1. Let \(\tilde{\sigma}\) be considered as a permutation of size n−1 given by \((\tilde{\pi}_{1}, \dots, \tilde{\pi}_{n-1})\). Then using the formula for w in (4.2) to separate out the last term in the product, we obtain

$$ \sum_{\substack{j=1 \\\pi' = \tilde{\pi} \tau_{n-2} \cdots\tau _j}}^{n-1} x_{\pi'_j} w\bigl( \pi'\bigr) = \frac{1}{x_{\pi_1}+ \cdots+ x_{\pi_n}} \sum _{\substack{j=1 \\\sigma' = \tilde{\sigma} \tau_{n-2} \cdots \tau_j}}^{n-1} x_{\sigma'_j} w\bigl( \sigma'\bigr) $$
(4.5)

The induction assumption now applies to the sum on the right hand side, and hence (4.3) yields

$$\begin{aligned} &x_{\pi_n} w(\pi) + \sum_{\substack{j=1 \\\pi' = \tilde{\pi} \tau_{n-2} \cdots\tau _j}}^{n-1} x_{\pi'_j} w\bigl(\pi'\bigr) \\ &\quad =x_{\pi_n} w(\pi) + \frac{1}{x_{\pi_1}+ \cdots+ x_{\pi_n}} w(\tilde{\sigma}) (x_{\tilde{\pi}_1} + \cdots+ x_{\tilde{\pi }_{n-1}}), \\ &\quad =x_{\pi_n} w(\pi) + w(\tilde{\pi}) (x_{\tilde{\pi}_1} + \cdots + x_{\tilde{\pi}_{n-1}}). \end{aligned}$$

We now distinguish two cases: either τ n−1 acts trivially on π or not. In the first case, set \(\tilde{\pi} = \pi\) and we immediately obtain the left-hand side of (4.3). In the second case, observe that w(π) as in (4.2) satisfies the following recursion if τ j acts non-trivially

$$w(\pi\tau_j) = \frac{x_{\pi_1} + \cdots+ x_{\pi_j}}{x_{\pi_1} + \cdots+ x_{\pi_{j-1}} + x_{\pi_{j+1}}} w(\pi). $$

Using this for j=n−1 and \(x_{\tilde{\pi}_{1}} + \cdots+ x_{\tilde {\pi}_{n-1}} = x_{\pi_{1}} + \cdots+ x_{\pi_{n-2}} + x_{\pi_{n}}\) yields the left-hand side of (4.3). □

When P is the n-antichain, then \({\mathcal{L}}= S_{n}\). In this case, the probability distribution of Theorem 4.5 has been studied in a completely different context by Hendricks [20, 21] and is known in the literature as the Tsetlin library [36], which we now describe. Suppose that a library consists of n books b 1,…,b n on a single shelf. Assume that only one book is picked at a time and is returned before the next book is picked up. The book b i is picked with probability x i and placed at the end of the shelf.

We now explain why promotion on the n-antichain is the Tsetlin library. A given ordering of the books can be identified with a permutation π. The action of ∂ k on π gives πτ k ⋯τ n−1 by (2.3), where now all the τ i ’s satisfy the braid relation since none of the π j ’s are comparable. Thus the kth element in π is moved all the way to the end. The probability with which this happens is \(x_{\pi_{k}}\), which makes this process identical to the action of the Tsetlin library.

The stationary distribution of the Tsetlin library is a special case of Theorem 4.5. In this case, Z P of Remark 4.6 also has a nice product formula, leading to the probability distribution,

$$ w(\pi) = \prod_{i=1}^{n} \frac{x_{\pi_{i}}}{x_{\pi_1}+ \cdots+ x_{\pi_i}}. $$
(4.6)

Letac [24] considered generalizations of the Tsetlin library to rooted trees (meaning that each element in P besides the root has precisely one successor). Our results hold for any finite poset P.

Theorem 4.7

The stationary state weight w(π) of the linear extension \(\pi\in{ \mathcal{L}}(P)\) of the transposition graph is given by

$$ w(\pi) = \prod_{i=1}^{n} x_{\pi_{i}}^{i-\pi_{i}} , $$
(4.7)

assuming w(e)=1.

Proof

To prove the above result, we need to show that it satisfies the master equation (3.1), rewritten as

$$ w(\pi) \Biggl(\sum_{i=1}^n x_{\pi_i} \Biggr) = \sum_{j=1}^n x_{\pi^{(j)}_j} w\bigl(\pi^{(j)}\bigr), $$
(4.8)

where π (j)=πτ j . Let us compare π (j) and π. By definition, they differ at the positions j and j+1 at most. Either π (j)=π, or \(\pi^{(j)}_{j} = \pi_{j+1}\) and \(\pi ^{(j)}_{j+1} = \pi_{j}\). In the former case, we get a contribution to the right hand side of (4.8) of \(x_{\pi_{j}} w(\pi)\), whereas in the latter, \(x_{\pi_{j+1}} w(\pi^{(j)})\). But note that in the latter case by (4.7)

$$\frac{w(\pi^{(j)})}{w(\pi)} = \frac{x_{\pi_{j+1}}^{j-\pi_{j+1}} x_{\pi_{j}}^{j+1-\pi_{j}} }{x_{\pi_{j}}^{j-\pi_{j}} x_{\pi_{j+1}}^{j+1-\pi_{j+1}} } = \frac {x_{\pi_{j}}}{x_{\pi_{j+1}}}, $$

and the contribution is again \(x_{\pi_{j}} w(\pi)\). Thus the jth term on the right matches that on the left, and this completes the proof. □

5 Partition functions and eigenvalues for rooted forests

For a certain class of posets, we are able to give an explicit formula for the probability distribution for the promotion graph. Note that this involves computing the partition function Z P (see Remark 4.6). We can also specify all eigenvalues and their multiplicities of the transition matrix explicitly.

5.1 Main results

Before we can state the main theorems of this section, we need to make a couple of definitions. A rooted tree is a connected poset, where each node has at most one successor. Note that a rooted tree has a unique largest element. A rooted forest is a union of rooted trees. A lower set (resp., upper set) S in a poset is a subset of the nodes such that if x∈S and y⪯x (resp., y⪰x), then also y∈S. We first give the formula for the partition function.

Theorem 5.1

Let P be a rooted forest of size n and let x ⪯i =∑ j⪯i x j . The partition function for the promotion graph is given by

$$ Z_P = \prod_{i=1}^n \frac{x_{\preceq i}}{x_1 + \cdots+ x_i}. $$
(5.1)

Proof

We need to show that w′(π):=Z P w(π) with w(π) given by (4.1) satisfies

$$\sum_{\pi\in{ \mathcal{L}}(P)} w'(\pi) = 1. $$

We shall do so by induction on n. Assume that the formula is true for all rooted forests of size n−1. The main idea is that the last entry of π in one-line notation has to be a maximal element of one of the trees in the poset. Let P=T 1∪T 2∪⋯∪T k , where each T i is a tree. Moreover, let \(\hat{T}_{i}\) denote the maximal element of T i . Then

$$ \sum_{\pi\in{ \mathcal{L}}(P)} w'(\pi) = \sum _{i=1}^k \sum_{\sigma\in{ \mathcal{L}}(P \setminus\{\hat{T}_i\})} w'( \sigma\hat{T}_i ). $$

Using (4.1) and (5.1)

$$ w'( \sigma\hat{T}_i ) = w'(\sigma) \frac{x_{\preceq\hat{T}_i}}{x_1+\cdots+x_n}, $$

which leads to

$$ \sum_{\pi\in{ \mathcal{L}}(P)} w'(\pi) = \sum _{i=1}^k \frac{x_{\preceq\hat{T}_i}}{x_1+\cdots+x_n} \sum _{\sigma\in{ \mathcal{L}}(P \setminus\{\hat{T}_i\})} w'( \sigma). $$

By the induction assumption, the rightmost sum is 1, and since each x j occurs in one and only one numerator of the sums over i, an easy simplification leads to the desired result, □

Let L be a finite poset with smallest element \(\hat{0}\) and largest element \(\hat{1}\). Following [10, Appendix C], one may associate to each element x∈L a derangement number d x defined as

$$ d_x = \sum _{y\succeq x} \mu(x,y) f\bigl([y,\hat{1}]\bigr), $$
(5.2)

where μ(x,y) is the Möbius function for the interval [x,y]:={z∈L∣x⪯z⪯y} [32, Sect. 3.7] and \(f([y,\hat{1}])\) is the number of maximal chains in the interval \([y,\hat{1}]\).

A permutation is a derangement if it does not have any fixed points. A linear extension π is called a poset derangement if it is a derangement when considered as a permutation. Let \(\mathfrak{d}_{P}\) be the number of poset derangements of the poset P.

A lattice L is a poset in which any two elements have a unique supremum (also called join) and a unique infimum (also called meet). For x,y∈L the join is denoted by x∨y, whereas the meet is x∧y. For an upper semi-lattice we only require the existence of a unique supremum of any two elements.

Theorem 5.2

Let P be a rooted forest of size n and M the transition matrix of the promotion graph of Sect. 3.4. Then

where x S =∑ i∈S x i and d S is the derangement number in the lattice L (by inclusion) of upper sets in P. In other words, for each subset S⊆[n], which is an upper set in P, there is an eigenvalue x S with multiplicity d S .

The proof of Theorem 5.2 will be given in Sect. 6. As we will see in Lemma 6.5, the action of the operators in the promotion graph of Sect. 3.4 for rooted forests have a Tsetlin library type interpretation of moving books to the end of a stack (up to reordering).

When P is a union of chains, which is a special case of rooted forests, we can express the eigenvalue multiplicities directly in terms of the number of poset derangements.

Theorem 5.3

Let P=[n 1]+[n 2]+⋯+[n k ] be a union of chains of size n whose elements are labeled consecutively within chains. Then

where \(\mathfrak{d}_{\emptyset}=1\).

The proof of Theorem 5.3 is given in Sect. 5.2.

Corollary 5.4

For P a union of chains, we have the identity

$$ \bigl|{\mathcal{L}}(P)\bigr| = \sum_{\substack{ S \subseteq[n]\\ S\ \mathrm{upper}\ \mathrm{set}\ \mathrm{in}\ P}} d_S = \sum_{\substack{ S \subseteq[n]\\ S\ \mathrm{lower}\ \mathrm{set}\ \mathrm{in}\ P}} \mathfrak{d}_S . $$
(5.3)

Note that the antichain is a special case of a rooted forest and in particular a union of chains. In this case, the Markov chain is the Tsetlin library and all subsets of [n] are upper (and lower) sets. Hence Theorem 5.2 specializes to the results of Donnelly [15], Kapoor and Reingold [23], and Phatarfod [27] for the Tsetlin library.

The case of unions of chains, which are consecutively labeled, can be interpreted as looking at a parabolic subgroup of S n . If there are k chains of lengths n i for 1≤i≤k, then the parabolic subgroup is \(S_{n_{1}} \times\cdots\times S_{n_{k}}\). In the realm of the Tsetlin library, there are n i books of the same color. The Markov chain consists of taking a book at random and placing it at the end of the stack.

5.2 Proof of Theorem 5.3

We deduce Theorem 5.3 from Theorem 5.2 by which the matrix M has eigenvalues indexed by upper sets S with multiplicity d S . We need to show that \(\mathfrak{d}_{P \setminus S} = d_{S}\).

Let P be a union of chains and L the lattice of upper sets of P. The Möbius function of P is the product of the Möbius functions of each chain. This implies that the only upper sets of P with a nonzero entry of the Möbius function are the ones with unions of the top element in each chain.

Since upper sets of unions of chains are again unions of chains, it suffices to consider d ∅ for P as d S can be viewed as d ∅ for P∖S. By (5.2) we have

$$d_\emptyset= \sum_S \mu(\emptyset, S) f \bigl([S,\hat{1}]\bigr), $$

where the sum is over all upper sets of P containing only top elements in each chain. Recall that \(f([S,\hat{1}])\) is the number of chains from S to \(\hat {1}\) in L. By inclusion–exclusion, the claim that \(d_{\emptyset}= \mathfrak{d}_{P}\) is the number of poset derangements of P, that is, the number of linear extensions of P without fixed points, follows from the next lemma.

Lemma 5.5

Let P=[n 1]+[n 2]+⋯+[n k ]. Fix I⊆[k] and let S⊆P be the upper set containing the top element of the ith chain of P for all i∈I. Then \(f([S,\hat{1}])\) is equal to the number of linear extensions of P that fix at least one element of the ith chain of P for all i∈I.

Proof

Let n=n 1+n 2+⋯+n k denote the number of elements in P. Let N 1=0 and define N i =n 1+⋯+n i−1 for all 2≤i≤k. We label the elements of P consecutively so that N i +1,N i +2,…,N i+1 label the elements of the ith chain of P for all 1≤i≤k.

The linear extensions of P are in bijection with words w of length n in the alphabet \(\mathcal{E}:= \{e_{1}, e_{2}, \ldots, e_{k}\}\) with n i instances of each letter e i . Indeed, given a linear extension π of P, we associate such a word w to π by setting w j =e i if π j ∈{N i +1,…,N i+1}; i.e., if j lies in the ith column of P under the extension π. For the remainder of the proof, we will identify a linear extension π (and properties of π) with its corresponding word w. We also view e i as standard basis vectors in \(\mathbb{Z}^{k}\).

For any 1≤i≤k and 1≤j≤n i , the element N i +j is fixed by w if and only if w satisfies the following two conditions:

  • \(w_{N_{i}+j} = e_{i}\) (i.e., w sends N i +j to the ith column of P) and

  • the restriction of w to its first N i +j letters, which we denote \(w|_{[1,\ldots,N_{i}+j]}\), contains exactly j instances of the letter e i (i.e., N i +j is the jth element of the ith column of P under the extension w).

Moreover, it is clear that the set of all j∈{1,…,n i } such that w fixes N i +j is an interval of the form [a i ,b i ].

With I and S defined as in the statement of the lemma, let

$$ n'_i:= \begin{cases} n_i -1 & \text{if } i \in I, \\ n_i & \text{if } i \notin I. \end{cases} $$

Similarly, define \(N'_{1} = 0\) and \(N'_{i} = n'_{1} + \cdots+ n'_{i-1}\) for i≥2. We see that \(f([S,\hat{1}])\) counts the number of words of length n−|I| in the alphabet \(\mathcal {E}\) with \(n'_{j}\) instances of each letter e j . This is because S corresponds to the element δ I defined by

$$ \delta_I(i) = \begin{cases} 1 & \text{if } i \in I, \\ 0 & \text{if } i \notin I, \end{cases} $$

of L. The maximal chains in L from δ I to (n 1,n 2,…,n k ) are lattice paths in \(\mathbb{Z}^{k}\) with steps in the directions of the standard basis vectors e 1,e 2,…,e k .

Having established this notation, we are ready to prove the main statement of the Lemma. Let \(\mathcal{W}\) denote the collection of all words in the alphabet \(\mathcal{E}\) of length n with n j instances of each letter e j that fix an element of the ith chain of P for all i∈I. Let \(\mathcal{W}'\) denote the collection of all words of length n−|I| in the alphabet \(\mathcal{E}\) with \(n'_{j}\) instances of each letter e j .

We define a bijection \(\varphi: \mathcal{W} \rightarrow\mathcal {W}'\) as follows. For each i∈I, suppose \(w \in\mathcal{W}\) fixes the elements N i +a i ,…,N i +b i from the ith chain of P. We define φ(w) to be the word obtained from w by removing the letter e i in position \(w_{N_{i} + b_{i}}\) for each i∈I. Clearly, φ(w) has length n−|I| and \(n'_{j}\) instances of each letter e j .

Conversely, given \(w' \in\mathcal{W}'\), let J i be the set of indices \(N'_{i}+j\) with \(0 \leq j \leq n'_{i}\) such that \(w'|_{[1,\ldots,N'_{i}+j]}\) contains exactly j instances of the letter e i . Here we allow j=0 since it is possible that there are no instances of the letter e i among the first \(N'_{i}\) letters of w′. Again, it is clear that each J i is an interval of the form \([N'_{i} + c_{i}, \ldots, N'_{i}+d_{i}]\) and \(w'_{N_{i}+j} = e_{i}\) for all j∈[c i +1,…,d i ], though it is possible that \(w'_{N'_{i}+c_{i}} \neq e_{i}\). Thus we define φ −1(w′) to be the word obtained from w′ by inserting the letter e i after \(w'_{N'_{i}+d_{i}}\) for all i∈I. □

We illustrate the proof of Lemma 5.5 in the following example.

Example 5.6

Let P=[3]+[4]+[2]+[5], I={2,4}, and consider the linear extension

$$\pi:=1\; 10\; 4\; 8\; \mathbf{5}\; \mathbf{6}\; 2\; 3\; 11\; 9\; 7\; \mathbf{12} \; \mathbf{13}\; \mathbf{14}, $$

which corresponds to the word

$$w = e_1 e_4 e_2 | e_3 \mathbf{e_2} \mathbf{e_2} e_1 | e_1 e_4 | e_3 e_2 \mathbf{e_4} \mathbf{e_4} \mathbf{e_4}. $$

Here we have divided the word according to the chains of P. The fixed points of π in the second and fourth chains of P are shown in bold, along with their corresponding entries of the word w. In this case, φ(w)=e 1 e 4 e 2 e 3 e 2 e 1 e 1 e 4 e 3 e 2 e 4 e 4.

Conversely, consider

$$w' = e_2 e_1 e_4 | e_3 e_3 e_1 | e_2 e_1 | e_2 e_4 e_4 e_4 \in\mathcal{W}'. $$

Again, we have partitioned w′ into blocks of size \(n'_{i}\) for each i=1,…,4. In this case, J 2={4} and J 4={10,11,12}, so φ −1(w′) is the following word, with the inserted letters shown in bold:

$$\varphi^{-1}\bigl(w'\bigr) = e_1 e_1 e_4 | e_3 \mathbf{e_2} e_1 e_3 | e_2 e_1 | e_2 e_4 e_4 e_4 \mathbf{e_4}. $$

Remark 5.7

The initial labeling of P in the proof of Lemma 5.5 is essential to the proof. For example, let P be the poset [2]+[2] with two chains, each of length two. Labeling the elements of P so that 1<2 and 3<4 admits two derangements: 3142 and 3412. On the other hand, labeling the elements of P so that 1<4 and 2<3 only admits one derangement: 2143. In either case, the eigenvalue 0 of M has multiplicity 2.

6 \(\mathcal {R}\)-Trivial monoids

In this section, we provide the proof of Theorem 5.2. We first note that in the case of rooted forests the monoid generated by the relabeled promotion operators of the promotion graph is \(\mathcal {R}\)-trivial (see Sects. 6.1 and 6.2). Then we use a generalization of Brown’s theory [10] for Markov chains associated to left regular bands (see also [6, 7]) to \(\mathcal {R}\)-trivial monoids. This is, in fact, a special case of Steinberg’s results [34, Theorems 6.3 and 6.4] for monoids in the pseudovariety DA as stated in Sect. 6.3. The proof of Theorem 5.2 is given in Sect. 6.4.

6.1 \(\mathcal {R}\)-Trivial monoids

A finite monoid \(\mathcal {M}\) is a finite set with an associative multiplication and an identity element. Green [18] defined several preorders on \(\mathcal {M}\). In particular, for \(x,y\in \mathcal {M}\) right and left order is defined as

$$ \begin{aligned} & x \le_{\mathcal {R}} y \quad \text{if }y=xu\mbox{ for some }u\in \mathcal {M}, \\ & x \le_{\mathcal {L}} y \quad\text{if }y=ux\mbox{ for some }u\in \mathcal {M}. \end{aligned} $$
(6.1)

(Note that this is, in fact, the opposite convention used by Green). This ordering gives rise to equivalence classes (\(\mathcal {R}\)-classes or \(\mathcal {L}\)-classes)

$$ \begin{aligned} & x \; \mathcal {R}\; y \quad\text{if and only if }x\mathcal {M}= y \mathcal {M}, \\ & x \; \mathcal {L}\; y \quad\text{if and only if }\mathcal {M}x = \mathcal {M}y. \end{aligned} $$

The monoid \(\mathcal {M}\) is said to be \(\mathcal {R}\)-trivial (resp., \(\mathcal {L}\)-trivial) if all \(\mathcal {R}\)-classes (resp., \(\mathcal {L}\)-classes) have cardinality one.

Remark 6.1

A monoid \(\mathcal {M}\) is a left regular band if x 2=x and xyx=xy for all \(x,y\in \mathcal {M}\). It is not hard to check (see also [3, Example 2.4]) that left regular bands are \(\mathcal {R}\)-trivial.

Schocker [31] introduced the notion of weakly ordered monoids which is equivalent to the notion of \(\mathcal {R}\)-triviality [3, Theorem 2.18] (the proof of which is based on ideas by Steinberg and Thiéry).

Definition 6.2

A finite monoid \(\mathcal {M}\) is said to be weakly ordered if there is a finite upper semi-lattice \((L^{\mathcal {M}},\preceq)\) together with two maps \(\operatorname {supp}, \operatorname {des}:\mathcal {M}\to L^{\mathcal {M}}\) satisfying the following axioms:

  1. (i)

    \(\operatorname {supp}\) is a surjective monoid morphism, that is, \(\operatorname {supp}(xy) = \operatorname {supp}(x) \vee \operatorname {supp}(y)\) for all \(x,y \in \mathcal {M}\) and \(\operatorname {supp}(\mathcal {M})=L^{\mathcal {M}}\).

  2. (ii)

    If \(x,y \in \mathcal {M}\) are such that \(xy\le_{\mathcal {R}} x\), then \(\operatorname {supp}(y) \preceq \operatorname {des}(x)\).

  3. (iii)

    If \(x,y \in \mathcal {M}\) are such that \(\operatorname {supp}(y) \preceq \operatorname {des}(x)\), then xy=x.

Theorem 6.3

[3, Theorem 2.18] Let \(\mathcal {M}\) be a finite monoid. Then \(\mathcal {M}\) is weakly ordered if and only if \(\mathcal {M}\) is \(\mathcal {R}\)-trivial.

If \(\mathcal {M}\) is \(\mathcal {R}\)-trivial, then for each \(x\in \mathcal {M}\) there exists an exponent of x such that x ω x=x ω. In particular, x ω is idempotent, that is, (x ω)2=x ω.

Given an \(\mathcal {R}\)-trivial monoid \(\mathcal {M}\), one might be interested in finding the underlying semi-lattice \(L^{\mathcal {M}}\) and maps \(\operatorname {supp},\operatorname {des}\).

Remark 6.4

The upper semi-lattice \(L^{\mathcal {M}}\) and the maps \(\operatorname {supp},\operatorname {des}\) for an \(\mathcal {R}\)-trivial monoid \(\mathcal {M}\) can be constructed as follows:

  1. (i)

    \(L^{\mathcal {M}}\) is the set of left ideals \(\mathcal {M}e\) generated by the idempotents \(e\in \mathcal {M}\), ordered by reverse inclusion.

  2. (ii)

    \(\operatorname {supp}:\mathcal {M}\to L^{\mathcal {M}}\) is defined as \(\operatorname {supp}(x) = \mathcal {M}x^{\omega}\).

  3. (iii)

    \(\operatorname {des}: \mathcal {M}\to L^{\mathcal {M}}\) is defined as \(\operatorname {des}(x)=\operatorname {supp}(e)\), where e is some maximal element in the set \(\{y\in \mathcal {M}\mid xy=x\}\) with respect to the preorder \(\le_{\mathcal {R}}\).

The idea of associating a lattice (or semi-lattice) to certain monoids has been used for a long time in the semigroup community [13].

6.2 \(\mathcal {R}\)-Triviality of the promotion monoid

Now let P be a rooted forest of size n and \(\hat{\partial}_{i}\) for 1≤i≤n the operators on \({\mathcal{L}}(P)\) defined by the promotion graph of Sect. 3.4. That is, for \(\pi,\pi' \in{ \mathcal{L}}(P)\), the operator \(\hat{\partial}_{i}\) maps π to π′ if \(\pi' = \pi\partial _{\pi^{-1}_{i}}\). We are interested in the monoid \(\mathcal {M}^{\hat{\partial}}\) generated by \(\{ \hat{\partial}_{i} \mid1\le i \le n\}\).

Lemma 6.5

Let P and \(\hat{\partial}_{i}\) be as above, and \(\pi\in{ \mathcal{L}}(P)\). Then \(\pi \hat{\partial}_{i}\) is the linear extension in \({\mathcal{L}}(P)\) obtained from π by moving the letter i to position n and reordering all letters j⪰i.

Proof

Suppose \(\pi_{i}^{-1} = k\). Then the letter i is in position k in π. Furthermore by definition \(\pi \hat{\partial}_{\pi^{-1}_{i}} = \pi \hat{\partial}_{k} = \pi\tau_{k} \tau_{k+1} \cdots\tau_{n-1}\). Since π is a linear extension of P, all comparable letters are ordered within π. Hence τ k either tries to switch i with a letter j⪰i or an incomparable letter j. In the case j⪰i, τ k acts as the identity. In the other case, τ k switches the elements. In the first (resp., second) case, we repeat the argument with i replaced by its unique successor j (resp., i) and τ k replaced by τ k+1, etc. It is not hard to see that this results in the claim of the lemma. □

Example 6.6

Let P be the union of a chain of length 3 and a chain of length 2, where the first chain is labeled by the elements {1,2,3} and the second chain by {4,5}. Then \(41235 \hat{\partial}_{1} = 41253\), which is obtained by moving the letter 1 to the end of the word and then reordering the letters {1,2,3}, so that the result is again a linear extension of P.

As another example, let P be the rooted tree of Fig. 7. Then \(31245 \in{ \mathcal{L}}(P)\). It is easy to check from the definition that \(31245 \; \hat{\partial}_{3} = 12345\). In accordance with Lemma 6.5, we can move the letter 3 to the back to obtain 12453. However, then the letters 3,4,5 in j⪰3 are out of order and need to be reordered to obtain 12345.

Fig. 7
figure 7

Rooted tree used in Example 6.6

Full size image

Let \(x\in \mathcal {M}^{\hat{\partial}}\). The image of x is \(\operatorname {im}(x) = \{\pi x \mid\pi\in{ \mathcal{L}}(P)\}\). Furthermore, for each \(\pi\in \operatorname {im}(x)\), let \(\operatorname {fiber}(\pi,x) = \{ \pi ' \in{ \mathcal{L}}(P) \mid\pi= \pi' x\}\). Let \(\operatorname{rfactor}(x)\) be the maximal common right factor of all elements in \(\operatorname {im}(x)\), that is, all elements \(\pi\in \operatorname {im}(x)\) can be written as \(\pi= \pi_{1} \cdots\pi_{m} \operatorname{rfactor}(x)\) and there is no bigger right factor for which this is true. Let us also define the set of entries in the right factor \(\operatorname {Rfactor}(x) = \{ i \mid i\in\operatorname{rfactor}(x) \}\). Note that since all elements in the image set of x are linear extensions of P, \(\operatorname {Rfactor}(x)\) is an upper set of P.

By Lemma 6.5, linear extensions in \(\operatorname {im}(\hat{\partial}_{i})\) have as their last letter max P {j∣j⪰i}; this maximum is unique since P is a rooted forest. Hence it is clear that \(\operatorname {im}(\hat{\partial}_{i} x) \subseteq \operatorname {im}(x)\) for any \(x\in \mathcal {M}^{\hat{\partial}}\) and 1≤i≤n. In particular, if \(x\le_{\mathcal {L}}y\), that is y=ux for some \(u\in \mathcal {M}^{\hat{\partial}}\), then \(\operatorname {im}(y) \subseteq \operatorname {im}(x)\). Hence x,y can only be in the same \(\mathcal {L}\)-class if \(\operatorname {im}(x)=\operatorname {im}(y)\).

Fix \(x \in \mathcal {M}^{\hat{\partial}}\) and let the set I x ={i 1,…,i k } be maximal such that \(\hat{\partial}_{i_{j}} x = x\) for 1≤j≤k. The following holds.

Lemma 6.7

If x is an idempotent, then \(\operatorname {Rfactor}(x) = I_{x}\).

Proof

Recall that the operators \(\hat{\partial}_{i}\) generate \(\mathcal {M}^{\hat{\partial}}\). Hence we can write \(x = \hat{\partial}_{\alpha_{1}} \cdots \hat{\partial}_{\alpha_{m}}\) for some α j ∈[n].

The condition \(\hat{\partial}_{i} x = x\) is equivalent to the condition that for every \(\pi\in \operatorname {im}(\hat{\partial}_{i})\) there is a \(\pi'\in \operatorname {im}(x)\) such that \(\operatorname {fiber}(\pi, \hat{\partial}_{i}) \subseteq \operatorname {fiber}(\pi',x)\) and π′=πx. Since x is idempotent we also have π′=π′x. The first condition \(\operatorname {fiber}(\pi, \hat{\partial}_{i}) \subseteq \operatorname {fiber}(\pi ',x)\) makes sure that the fibers of x are coarser than the fibers of \(\hat{\partial}_{i}\); this is a necessary condition for \(\hat{\partial}_{i} x = x\) to hold (recall that we are acting on the right) since the fibers of \(\hat{\partial}_{i} x\) are coarser than the fibers of \(\hat{\partial}_{i}\). The second condition π′=πx ensures that \(\operatorname {im}(\hat{\partial}_{i} x) = \operatorname {im}(x)\). Conversely, if the two conditions hold, then certainly \(\hat{\partial}_{i} x = x\). Since x 2=x is an idempotent, we hence must have \(\hat{\partial}_{\alpha_{j}} x = x\) for all 1≤j≤m.

Now let us consider \(x\hat{\partial}_{\alpha_{j}}\). If \(\alpha_{j} \notin \operatorname {Rfactor}(x)\), then, by Lemma 6.5, we have \(\operatorname {Rfactor}(x) \subsetneq \operatorname {Rfactor}(x\hat{\partial}_{\alpha_{j}})\) and hence \(|\mathrm{im}\,(x\hat{\partial}_{\alpha_{j}})|< |\mathrm{im}\,(x)|\), which contradicts the fact that x 2=x. Therefore, \(\alpha_{j}\in \operatorname {Rfactor}(x)\).

Now suppose \(\hat{\partial}_{i}x=x\). Then \(x=\hat{\partial}_{i} \hat{\partial}_{\alpha_{1}} \cdots \hat{\partial}_{\alpha_{m}}\) and by the same arguments as above \(i\in \operatorname {Rfactor}(x)\). Hence \(I_{x} \subseteq \operatorname {Rfactor}(x)\). Conversely, suppose \(i\in \operatorname {Rfactor}(x)\). Then \(x\hat{\partial}_{i}\) has the same fibers as x (but possibly a different image set since \(\operatorname{rfactor}(x\hat{\partial}_{i}) = \operatorname{rfactor}(x) \hat{\partial}_{i}\) which can be different from \(\operatorname{rfactor}(x)\)). This implies \(x\hat{\partial}_{i} x =x\). Hence considering the expression in terms of generators \(x= \hat{\partial}_{\alpha_{1}} \cdots \hat{\partial}_{\alpha_{m}} \hat{\partial}_{i} \hat{\partial}_{\alpha_{1}} \cdots \hat{\partial}_{\alpha_{m}}\), the above arguments imply that \(\hat{\partial}_{i} x = x\). This shows that \(\operatorname {Rfactor}(x) \subseteq I_{x}\) and hence \(I_{x} = \operatorname {Rfactor}(x)\). This proves the claim. □

Lemma 6.8

I x is an upper set of P for any \(x\in \mathcal {M}^{\hat{\partial}}\). More precisely, \(I_{x} = \operatorname {Rfactor}(e)\) for some idempotent \(e\in \mathcal {M}^{\hat{\partial}}\).

Proof

For any \(x\in \mathcal {M}^{\hat{\partial}}\), \(\operatorname{rfactor}(x) \subseteq \operatorname{rfactor}(x^{\ell})\) for any integer ℓ>0. Also, the fibers of x ℓ are coarser or equal to the fibers of x. Since the right factors can be of length at most n (the size of P) and \(\mathcal {M}^{\hat{\partial}}\) is finite, for ℓ sufficiently large we have (x ℓ)2=x ℓ, so that x ℓ is an idempotent. Now take a maximal idempotent e in the \(\ge_{\mathcal {R}}\) preorder such that ex=x (when I x =∅ we have ) which exists by the previous arguments. Then I e =I x which, by Lemma 6.7, is also \(\operatorname {Rfactor}(e)\). This proves the claim. □

Let M be the transition matrix of the promotion graph of Sect. 3.4. Define \(\mathcal {M}\) to be the monoid generated by {G i ∣1≤i≤n}, where G i is the matrix M evaluated at x i =1 and all other x j =0. We are now ready to state the main result of this section.

Theorem 6.9

\(\mathcal {M}\) is \(\mathcal {R}\)-trivial.

Remark 6.10

Considering the matrix monoid \(\mathcal {M}\) is equivalent to considering the abstract monoid \(\mathcal {M}^{\hat{\partial}}\) generated by \(\{\hat{\partial}_{i} \mid1\le i \le n\}\). Since the operators \(\hat{\partial}_{i}\) act on the right on linear extensions, the monoid \(\mathcal {M}^{\hat{\partial}}\) is \(\mathcal {L}\)-trivial instead of \(\mathcal {R}\)-trivial.

Example 6.11

Let P be the poset on three elements {1,2,3}, where 2 covers 1 and there are no further relations. The linear extensions of P are {123,132,312}. The monoid \(\mathcal {M}\) with \(\mathcal {R}\)-order, where an edge labeled i means right multiplication by G i , is depicted in Fig. 8. From the picture it is clear that the elements in the monoid are partially ordered. This confirms Theorem 6.9 that the monoid is \(\mathcal {R}\)-trivial.

Fig. 8
figure 8

Monoid \(\mathcal {M}\) in right order for the poset of Example 6.11

Full size image

Example 6.12

Now consider the poset P on three elements {1,2,3}, where 1 is covered by both 2 and 3 with no further relations. The linear extensions of P are {123,132}. This poset is not a rooted forest. The corresponding monoid in \(\mathcal {R}\)-order is depicted in Fig. 9. The two elements

$$ \begin{pmatrix} 0&1\\ 1&0 \end{pmatrix} \quad\text{and} \quad \begin{pmatrix} 1&0 \\ 0&1 \end{pmatrix} $$

are in the same \(\mathcal {R}\)-class. Hence the monoid is not \(\mathcal {R}\)-trivial, which is consistent with Theorem 6.9.

Fig. 9
figure 9

Monoid \(\mathcal {M}\) in right order for the poset of Example 6.12

Full size image

Proof of Theorem 6.9

By Theorem 6.3, a monoid is \(\mathcal {R}\)-trivial if and only if it is weakly ordered. We prove the theorem by explicitly constructing the semi-lattice \(L^{\mathcal {M}}\) and maps \(\operatorname {supp}, \operatorname {des}:\mathcal {M}^{\hat{\partial}} \to L^{\mathcal {M}}\) of Definition 6.2. In fact, since we work with \(\mathcal {M}^{\hat{\partial}}\), we will establish the left version of Definition 6.2 by Remark 6.10.

Recall that for \(x \in \mathcal {M}^{\hat{\partial}}\), we defined the set I x ={i 1,…,i k } to be maximal such that \(\hat{\partial}_{i_{j}} x = x\) for 1≤j≤k.

Define \(\operatorname {des}(x)=I_{x}\) and \(\operatorname {supp}(x) = \operatorname {des}(x^{\omega})\). By Lemma 6.7, for idempotents x we have \(\operatorname {supp}(x) = \operatorname {des}(x) = I_{x} = \operatorname {Rfactor}(x)\). Let \(L^{\mathcal {M}}= \{ \operatorname {Rfactor}(x) \mid x\in \mathcal {M}^{\hat{\partial}}, x^{2}=x \}\) which has a natural semi-lattice structure \((L^{\mathcal {M}},\preceq)\) by inclusion of sets. The join operation is union of sets.

Certainly by Lemma 6.7 and the definition of \(L^{\mathcal {M}}\), the map \(\operatorname {supp}\) is surjective. We want to show that in addition \(\operatorname {supp}(xy) = \operatorname {supp}(x) \vee \operatorname {supp}(y)\), where ∨ is the join in \(L^{\mathcal {M}}\). Recall that \(\operatorname {supp}(x) = \operatorname {des}(x^{\omega}) = \operatorname {Rfactor}(x^{\omega})\). If \(x = \hat{\partial}_{j_{1}} \cdots \hat{\partial}_{j_{m}}\) in terms of the generators and J x :={j 1,…,j m }, then, by Lemma 6.5, \(\operatorname {Rfactor}(x^{\omega})\) contains the upper set of J x in P plus possibly some more elements that are forced if the upper set of J x has only one successor in the semi-lattice of upper sets in P. A similar argument holds for y with J y . Now again by Lemma 6.5, \(\operatorname {supp}(xy) = \operatorname {Rfactor}((xy)^{\omega})\) contains the elements in the upper set of J x ∪J y , plus possibly more forced by the same reason as before. Hence \(\operatorname {supp}(xy) = \operatorname {supp}(x) \vee \operatorname {supp}(y)\). This shows that Definition 6.2(i) holds.

Suppose \(x,y\in \mathcal {M}^{\hat{\partial}}\) with \(yx \le_{\mathcal {L}} x\). Then there exists a \(z\in \mathcal {M}^{\hat{\partial}}\) such that zyx=x. Hence \(\operatorname {supp}(y) \preceq \operatorname {supp}(zy) \preceq I_{x} =\operatorname {des}(x)\) by Lemmas 6.7 and 6.8. Conversely, if \(x,y\in \mathcal {M}^{\hat{\partial}}\) are such that \(\operatorname {supp}(y) \preceq \operatorname {des}(x)\), then by the definition of \(\operatorname {des}(x)\) we have \(\operatorname {supp}(y) \preceq I_{x}\), which is the list of indices of the left stabilizers of x. By the definition of \(\operatorname {supp}(y)\) and the proof of Lemma 6.7, y ω can be written as a product of \(\hat{\partial}_{i}\) with \(i\in \operatorname {supp}(y)\). The same must be true for y. Hence yx=x, which shows that the left version of (ii) and (iii) of Definition 6.2 hold.

In summary, we have shown that \(\mathcal {M}^{\hat{\partial}}\) is weakly ordered in \(\mathcal {L}\)-preorder and hence \(\mathcal {L}\)-trivial. This implies that \(\mathcal {M}\) is \(\mathcal {R}\)-trivial. □

Remark 6.13

In the proof of Theorem 6.9 we explicitly constructed the semi-lattice \(L^{\mathcal {M}}=\{ \operatorname {Rfactor}(x) \mid x\in \mathcal {M}^{\hat{\partial}}, x^{2}=x\}\) and the maps \(\operatorname {supp},\operatorname {des}: \mathcal {M}^{\hat{\partial}} \to L^{\mathcal {M}}\) of Definition 6.2. Here \(\operatorname {des}(x)= I_{x}\) is the set of indices I x ={i 1,…,i m } such that \(\hat{\partial}_{i_{j}} x =x\) for all 1≤j≤m and \(\operatorname {supp}(x) = \operatorname {des}(x^{\omega}) = I_{x^{\omega}} = \operatorname {Rfactor}(x^{\omega})\).

Example 6.14

Let P be the poset of Example 6.11. The monoid \(\mathcal {M}\) with \(\mathcal {R}\)-order, where an edge labeled i means right multiplication by G i , is depicted in Fig. 8. The elements are idempotent with \(\operatorname {supp}(x)=\operatorname {des}(x)=\emptyset,2,123,123\), 123, respectively. The only non-idempotent element is G 1 with \(\operatorname {supp}(G_{1})=123\) and \(\operatorname {des}(G_{1})=\emptyset\). The semi-lattice \(L^{\mathcal {M}}\) is the left lattice in Fig. 10. The right graph in Fig. 10 is the lattice L of all upper sets of P.

Fig. 10
figure 10

The left graph is the lattice \(L^{\mathcal {M}}\) of the weakly ordered monoid for the poset in Example 6.14. The right graph is the lattice L of all upper sets of P

Full size image

6.3 Eigenvalues and multiplicities for \(\mathcal {R}\)-trivial monoids

Let \(\mathcal {M}\) be a finite monoid (for example, a left regular band) and \(\{w_{x}\}_{x\in \mathcal {M}}\) a probability distribution on \(\mathcal {M}\) with transition matrix for the random walk given by

$$ M(c,d) = \sum _{xc=d} w_x $$
(6.2)

for \(c,d \in\mathcal{C}\), where \(\mathcal{C}\) is the set of maximal elements in \(\mathcal {M}\) under right order \(\ge_{\mathcal {R}}\). The set \(\mathcal{C}\) is also called the set of chambers.

Recall that by Remark 6.4 we can associate a semi-lattice \(L^{\mathcal {M}}\) and functions \(\operatorname {supp},\operatorname {des}:\mathcal {M}\to L^{\mathcal {M}}\) to an \(\mathcal {R}\)-trivial monoid \(\mathcal {M}\). For \(X\in L^{\mathcal {M}}\), define c X to be the number of chambers in \(\mathcal {M}_{\ge X}\), that is, the number of \(c\in\mathcal{C}\) such that \(c\ge_{\mathcal {R}} x\), where \(x\in \mathcal {M}\) is any fixed element with \(\operatorname {supp}(x)=X\).

Theorem 6.15

Let \(\mathcal {M}\) be a finite \(\mathcal {R}\)-trivial monoid with transition matrix M as in (6.2). Then M has eigenvalues

$$ \lambda_X = \sum_{\substack{y \\ \operatorname {supp}(y) \preceq X}} w_y $$
(6.3)

for each \(X\in L^{\mathcal {M}}\) with multiplicity d X recursively defined by

$$ \sum_{Y\succeq X} d_Y = c_X. $$
(6.4)

Equivalently,

$$ d_X = \sum_{Y \succeq X} \mu(X,Y) \; c_Y, $$
(6.5)

where μ is the Möbius function on \(L^{\mathcal {M}}\).

Brown [10, Theorem 4, p. 900] proved Theorem 6.15 in the case when \(\mathcal {M}\) is a left regular band. Theorem 6.15 is a generalization to the \(\mathcal {R}\)-trivial case. It is, in fact, a special case of a result of Steinberg [34, Theorems 6.3 and 6.4] for monoids in the pseudovariety DA. This was further generalized in [35].

6.4 Proof of Theorem 5.2

By Theorem 6.9, the promotion monoid \(\mathcal {M}\) is \(\mathcal {R}\)-trivial, hence Theorem 6.15 applies.

Let L be the lattice of upper sets of P and \(L^{\mathcal {M}}\) the semi-lattice of Definition 6.2 associated to \(\mathcal {R}\)-trivial monoids that is used in Theorem 6.15. Recall that for the promotion monoid \(L^{\mathcal {M}} = \{ \operatorname {Rfactor}(x) \mid x\in \mathcal {M}^{\hat{\partial}}, x^{2}=x \}\) by Remark 6.13. Now pick S∈L and let r=r 1…r m be any linear extension of P| S (denoting P restricted to S). By repeated application of Lemma 6.5, it is not hard to see that \(x = \hat{\partial}_{r_{1}} \cdots \hat{\partial}_{r_{m}}\) is an idempotent since \(r_{1} \dots r_{m} \subseteq \operatorname{rfactor}(x)\) and x only acts on this right factor and fixes it. \(\operatorname{rfactor}(x)\) is strictly bigger than r 1…r m if some further letters beyond r 1…r m are forced in the right factors of the elements in the image set. This can only happen if there is only one successor S′ of S in the lattice L. In this case, the element in S′∖S is forced as the letter to the left of r 1…r m and is hence part of \(\operatorname{rfactor}(x)\).

Recall that \(f([S,\hat{1}])\) is the number of maximal chains from S to the maximal element \(\hat{1}\) in L. Since L is the lattice of upper sets of P, this is precisely the number of linear extensions of P| P∖S . If S∈L has only one successor S′, then \(f([S,\hat{1}]) = f([S',\hat{1}])\). Equation (5.2) is equivalent to

$$f\bigl([S,\hat{1}]\bigr) = \sum_{T \succeq S} d_T $$

(see [10, Appendix C] for more details). Hence \(f([S,\hat {1}]) = f([S',\hat{1}])\) implies that d S =0 in the case when S has only one successor S′.

Now suppose \(S\in L^{\mathcal {M}}\) is an element of the smaller semi-lattice. Recall that c S of Theorem 6.15 is the number of maximal elements in \(x\in \mathcal {M}^{\hat{\partial}}\) with \(x\ge_{\mathcal {R}}s\) for some s with \(\operatorname {supp}(s)=S\). In \(\mathcal {M}\) the maximal elements in \(\mathcal {R}\)-order (or equivalently, in \(\mathcal {M}^{\hat{\partial}}\) in \(\mathcal {L}\)-order) form the chamber \(\mathcal{C}\) (resp., \(\mathcal{C}^{\hat{\partial}}\)) and are naturally indexed by the linear extensions in \({\mathcal{L}}(P)\). Namely, given \(\pi= \pi_{1} \ldots\pi_{n} \in{ \mathcal{L}}(P)\) the element \(x = \hat{\partial}_{\pi_{1}} \cdots \hat{\partial}_{\pi_{n}}\) is idempotent, maximal in \(\mathcal {L}\)-order and has as image set {π}. Conversely, given a maximal element x in \(\mathcal {L}\)-order it must have \(\operatorname{rfactor}(x)\in{ \mathcal{L}}(P)\). Given \(s\in \mathcal {M}^{\hat{\partial}}\) with \(\operatorname {supp}(s)=S\), only those maximal elements \(x\in \mathcal {M}^{\hat{\partial}}\) associated to \(\pi\in \operatorname {im}(s)\) are bigger than s. Hence for \(S\in L^{\mathcal {M}}\) we have \(c_{S} = f([S,\hat{1}])\).

The above arguments show that instead of \(L^{\mathcal {M}}\) one can also work with the lattice L of upper sets since any S∈L but \(S\notin L^{\mathcal {M}}\) comes with multiplicity d S =0 and otherwise the multiplicities agree.

The promotion Markov chain assigns a weight x i for a transition from π to π′ for \(\pi,\pi'\in{ \mathcal{L}}(P)\) if \(\pi'=\pi \hat{\partial}_{i}\). Recall that elements in the chamber \(\mathcal {C}^{\hat{\partial}}\) are naturally associated with linear extensions. Let \(x,x'\in\mathcal{C}^{\hat{\partial}}\) be associated to π,π′, respectively. That is, π=τx and π′=τx′ for all \(\tau\in{ \mathcal{L}}(P)\). Then \(x'= x \hat{\partial}_{i}\) since \(\tau(x \hat{\partial}_{i}) = (\tau x) \hat{\partial}_{i} = \pi \hat{\partial}_{i} = \pi'\) for all \(\tau\in{ \mathcal{L}}(P)\). Equivalently in the monoid \(\mathcal {M}\) we would have X′=G i X for \(X,X'\in\mathcal{C}\). Hence comparing with (6.2), setting the probability variables to \(w_{G_{i}}= x_{i}\) and w X =0 for all other \(X\in \mathcal {M}\), Theorem 6.15 implies Theorem 5.2.

Example 6.16

Figure 10 shows the lattice \(L^{\mathcal {M}}\) on the left and the lattice L of upper sets of P on the right, for the monoid displayed in Fig. 8. The elements 2,23,12 in L have only one successor and hence do not appear in \(L^{\mathcal {M}}\).

7 Outlook

Two of our Markov chains, the uniform promotion graph and the uniform transposition graph, are irreducible and have the uniform distribution as their stationary distributions. Moreover, the former is irreversible and has the advantage of having tunable parameters x 1,…,x n whose only constraint is that they sum to 1. Because of the irreversibility property, it is plausible that the mixing times for this Markov chain is smaller than the ones considered by Bubley and Dyer [5]. Hence the uniform promotion graph could have possible applications for uniformly sampling linear extensions of a large poset. This is certainly deserving of further study.

It would also be interesting to extend the results of Brown and Diaconis [4] (see also [1]) on rates of convergence to the Markov chains in this paper. For the Markov chains corresponding to \(\mathcal {R}\)-trivial monoids of Sect. 5, one can find polynomial time exponential bounds for the rates of convergence after ℓ steps of the form c ℓ k λ ℓ−k, where c is the number of chambers, λ=max i (1−x i ), and k is a parameter associated to the poset. More details on rates of convergence and mixing times can be found in [2].

In this paper, we have characterized posets, where the Markov chains for the promotion graph yield certain simple formulas for their eigenvalues and multiplicities. The eigenvalues have explicit expressions for rooted forests and there is a concrete combinatorial interpretation for the multiplicities as derangement numbers of permutations for unions of chains by Theorem 5.3. However, we have not covered all possible posets, whose promotion graphs have nice properties. For example, the non-zero eigenvalues of the transition matrix of the promotion graph of the poset in Example 3.1 are given by

$$x_3+x_4, \quad x_3, \quad0, \quad \text{and} \quad{-}x_1, $$

even though the corresponding monoid is not \(\mathcal {R}\)-trivial (in fact, it is not even aperiodic). Note that the last eigenvalue is negative. On the other hand, not all posets have this property. In particular, the poset with covering relations 1<2, 1<3, and 1<4 has six linear extensions, but the characteristic polynomial of its transition matrix does not factorize at all. It would be interesting to classify all posets with the property that all the eigenvalues of the transition matrices of the promotion Markov chain are linear in the probability distribution x i . In such cases, one would also like an explicit formula for the multiplicity of these eigenvalues. In this paper, this was only achieved for unions of chains. Further details are discussed in [2].