1 Introduction↩︎

One of the fundamental identities in the representation theory of partition algebras, due to Halverson and Lewandowski [1], is \[\label{eq:32Identity1} n^k=\sum_{\lambda\vdash n} f^\lambda m_{k}(\lambda), \qquad \text{for } n \geq 1,\tag{1}\] where the sum is over integer partitions \(\lambda\) of \(n\), \(f^\lambda\) is the number of standard Young tableaux (SYT) of shape \(\lambda\), and \(m_k(\lambda)\) is the number of vacillating tableaux of shape \(\lambda \vdash n\) and length \(2k\). Here a vacillating tableau of shape \(\lambda\) and length \(2k\) is a sequence of partitions \(\lambda_0=(n) \supseteq \lambda_{\frac{1}{2}} \subseteq \lambda_1 \supseteq \lambda_{\frac{3}{2}} \subseteq \lambda_2 \supseteq \cdots \subseteq \lambda_{k-1} \supseteq \lambda_{k-\frac{1}{2}} \subseteq \lambda_k =\lambda\) such that the sizes of consecutive partitions differ by exactly one. Following the English notation, we represent an integer partition \(\lambda=(a_1, a_2, \dots, a_k)_>\) by the Young diagram that contains \(a_j\) squares in the \(j\)-th row, which are aligned in the upper-left corner. Below is an example of a vacillating tableau of shape \(\lambda=(3,2,1) \vdash 6\) and length \(6\). \[\ytableausetup{boxsize=7pt} \ydiagram{6}, \; \ydiagram{5},\; \ydiagram{5,1},\, \ydiagram{4,1}, \;\ydiagram{4,2},\;\ydiagram{3,2},\;\ydiagram{3,2,1}.\]

In literature, there are two definitions of a vacillating tableau. The definition above was introduced in [1], while the term vacillating tableau was adopted from [2], where the combinatorial structures of crossings and nestings in matchings and set partitions were characterized. In [2] Chen et al. defined a vacillating tableauas a sequence of integer partitions that starts from the empty shape \(\emptyset\), where each \(\lambda_i\) is obtained from \(\lambda_{i-\frac{1}{2}}\) by adding a square, deleting a square, or doing nothing, depending on whether \(i\) is an integer or a half integer. When \(n \geq 2k\), the two notions are equivalent.

In this paper we use the definition from [1] as given in the first paragraph, while the notion defined in [2] will be referred to as a simplified vacillating tableau. Another way to understand vacillating tableauxis to view them as walks in Young’s lattice \(\mathbb{Y}\), the poset of all integer partitions ordered by inclusion. Explicitly, a vacillating tableau is a walk in the Hasse diagram of \(\mathbb{Y}\) starting from \((n)\) and using alternating down and up steps.

Identity 1 presents a combinatorial analogue of the Schur-Weyl duality between the symmetric group algebra and the partition algebra. In [1], Halverson and Lewandowski constructed an elegant combinatorial proof. Using a deletion-insertion algorithm based on jeu de taquin (jdt) and the Robinson-Schensted-Knuth (RSK) insertion algorithm, they associate to each integer sequence \(\boldsymbol{i} \in [n]^k\), where \([n]\mathrel{\vcenter{:}}=\{ 1, 2, \ldots, n\}\), a pair of tableaux of the same shape, one being a standard Young tableau and the other a vacillating tableau. Let \(\mu\) be any fixed partition of \(n\). Kratthenthaler [3] generalized Identity 1 to the following form, \[\begin{align} \label{Eq:Id2} f^\mu n^k = \sum_{\lambda \vdash n} f^\lambda \; m_k(\mu \rightarrow \lambda), \end{align}\tag{2}\] where \(m_k(\mu \rightarrow \lambda)\) is the number of vacillating tableaux of length \(2k\) from \(\mu\) to \(\lambda\), that is, sequences of partitions \(\lambda_0=\mu \supseteq \lambda_{\frac{1}{2}} \subseteq \lambda_1 \supseteq \lambda_{\frac{3}{2}} \subseteq \lambda_2 \supseteq \cdots \subseteq \lambda_{k-1} \supseteq \lambda_{k-\frac{1}{2}} \subseteq \lambda_k =\lambda\) such that consecutive partitions differ by exactly one square. Clearly \(m_k(\lambda) = m_k((n) \rightarrow \lambda)\). The proofs in [3] are presented in terms of Fomin’s growth diagrams ([4]–[6]).

In this paper, we consider Identities 1 and 2 in the content of differential posets, which contains Young’s lattice as a prototypical example. More precisely, we study certain alternating walks in the Hasse diagram of a differential poset and prove that Identity 2 , together with several of its analogs, follows from the structural property of differential posets by elementary combinatorial argument. We then present a new deletion–insertion algorithm that is simpler than the construction of Halverson and Lewandowski. Finally, we extend this new algorithm to obtain bijective proofs of these variant identities in Young’s lattice \(\mathbb{Y}\) and its Cartesian powers \(\mathbb{Y}^r\).

2 Walks in Differential Posets↩︎

Differential posets were introduced by Stanley [7] in 1988. They are a class of partially ordered sets with remarkable combinatorial and algebraic properties.

A typical example of a differential poset is Young’s lattice \(\mathbb{Y}\), which is \(1\)-differential. In general, \(\mathbb{Y}^r\) is \(r\)-differential. There are infinitely many irreducible \(r\)-differential posets; see the discussion in [7]. Among them, another one with significant combinatorial properties is the Fibonacci differential poset \(Z(r)\) described in [7].

Let \(P\) be a \(r\)-differential poset with the rank function \(\rho\) and \(P_n=\{x \in P: \;\rho(x)=n\}\) be the set of elements of rank \(n\). Given \(x \in P_n\), define \[C^-(x)=\{ y \in P:\;x \text{ covers } y\}, \qquad C^+(x)=\{y \in P:\;y \text{ covers } x\}.\] Note that both \(C^-(x)\) and \(C^+(x)\) are finite.

Let \(K\) be a field and \(KP\) be the \(K\)-vector space with basis \(P\), while \(\hat{K} P\) be the \(K\)-vector space of arbitrary linear combination of elements of \(P\). We can define two continuous linear operators, \(U\) and \(D\), from \(\hat{K} P \rightarrow \hat{K} P\), by \[U x = \sum_{y \in C^+(x)} y, \qquad D x = \sum_{y \in C^-(x)} y,\] for all \(x \in P\). We say that \(U\) is the up operator and \(D\) is the down operator. In addition, let \(I: \hat{K}P\rightarrow \hat{K}P\) be the identity transformation. A fundamental result proved in [7] asserts that if \(P\) is \(r\)-differential, then \[DU-UD=rI,\] where linear operators act right-to-left, e.g., \(DU x = D(Ux)\).

There is a symmetric bilinear form \(\langle \; ,\;\rangle: KP \times KP \rightarrow K\), defined by \[\langle x, y\rangle =\delta_{x,y} \qquad \text{for x,y \in P}.\] The form, as introduced in [7], was defined on \(\hat{K} P \times KP\) and continuous in the first coordinate. Here we only apply it to finite linear combinations of elements in \(P\), hence \(KP \times KP\). It follows that \[\langle \sum a_x x , \sum b_x x \rangle = \sum a_x b_x,\] when the variable \(x\) ranges over a finite subset of \(P\). The operators \(U\) and \(D\) are adjoint under this form, i.e., \[\langle Dx,y \rangle = \langle x, U y \rangle, \qquad \langle Ux, y \rangle = \langle x, Dy \rangle.\]

The problem of counting walks in the Hasse diagram of a differential poset was initially studied in [7]. In particular, various generating functions and formulas were given for walks following a special pattern \(w \in \{U, D\}^*\). The main goal of the present work is to use these ideas to extend Identities 1 and 2 to differential posets. The key ingredient of our approach is the following well-known identity that expands \((UD)^k\) as a linear combination of \(U^iD^j\).

This identity appears, for example, in [7]; earlier references trace back to Commet’s book [8]. It is also straightforward to prove by induction. Below we provide a simple combinatorial argument, which shows explicitly the connection to set partitions.

For a partition \(\pi\) of the set \([n]\), we write Arc\((\pi)\) for the set of pairs of integers \((i,j)\) such that \(i\) and \(j\) are consecutive elements in the same block of \(\pi\). One often represents set partitions by drawing a graph whose vertex set is \([n]\) and whose edge set is Arc(\(\pi\)). Such a graph is called the standard representation of \(\pi\). For example, the standard representation of \(\pi=\{\{1, 3, 4,7 \}, \{2,5\}, \{6\}\}\) is

A similar argument leads to the following expression, which will be used in our calculations later.

1 and 1 have appeared in [5] for dual graded graphs, which generalize differential posets. The results in [5] use the notion of \(r\)-colored diagonal set, another way to encode the cancellation of the \(D\) and \(U\) operators. The identities below therefore follow from the general theory developed in [5]. Here, however, we show that they can also be proved easily by elementary combinatorial arguments.

2.1 Down-up alternating walks↩︎

In this paper,we are interested in walks in an \(r\)-differential poset \(P\). Given \(x \in P_n\) and a word \(w \in \{U, D\}^*\), we have \(wx=\sum_{y} c_y y\), where \(c_y\) is the number of walks from \(x\) to \(y\) in the Hasse diagram of \(P\) of length \(|w|\), following the pattern of \(w\), in which \(U\) means an up step and \(D\) means a down step with respect to the rank of \(P\), and one should read the letters in the word \(w\) from right to left. Call such walks \(w\)-walks. In particular, we say that a \(w\)-walk with \(w=(UD)^k\) is a down-up alternating walk of length \(2k\). Explicitly, a down-up alternating walk from \(x\) to \(y\) of length \(2k\) is a sequence \(x=y_0 \geq y_{\frac{1}{2}} \leq y_1 \geq y_{\frac{3}{2}} \leq y_2 \geq \cdots \geq y_{k-\frac{1}{2}} \leq y_k =\lambda\) such that any two consecutive elements are adjacent in the Hasse diagram of \(P\). If \(x \in P_n\), then clearly \(y_i \in P_n\) and \(y_{i+\frac{1}{2}} \in P_{n-1}\) for any integer \(i\). We denote by \(m_k(x \rightarrow y)\) the number of down-up alternating walks from \(x\) to \(y\) and of length \(2k\).

Let \(e(x)\) be the number of saturated chains from \(\hat{0}\) to \(x\). In other words, \(e(x)\) is the \(U^n\)-walk from \(\hat{0}\) to \(x\) if \(x \in P_n\), which can also be expressed as \(e(x)= \langle D^n x, \hat{0}\rangle\).

In Young’s lattice, when \(x\) is the integer partition \(\lambda\), we have \(r=1\) and \(e(\lambda) = f^\lambda\), the number of standard Young tableaux of shape \(\lambda\). Hence Identity 2 is a special case of 4 .

Similarly, one can consider down-up alternating walks of odd length \(2k+1\). That is, a sequence \(x=y_0 \geq y_{\frac{1}{2}} \leq y_1 \geq y_{\frac{3}{2}} \leq y_2 \geq \cdots \geq y_{k-\frac{1}{2}} \leq y_k \geq y_{k+\frac{1}{2}}=\lambda\) such that \(y_i \in P_n\) and \(y_{i+\frac{1}{2}} \in P_{n-1}\) for any integer \(i\). Denote by \(m_{k+\frac{1}{2}}(x \rightarrow y)\) the number of down-up alternating walks of length \(2k+1\).

2.2 Up-down alternating walks↩︎

In this subsection we consider a variant of the down-up alternating walks that begins with an up step. Explicitly, an up-down alternating walk from \(x \in P_n\) in an \(r\)-differential poset \(P\) is a sequence \(x=y_0 \leq y_{\frac{1}{2}} \geq y_1 \leq y_{\frac{3}{2}} \geq y_2 \geq \cdots\) such that \(y_i \in P_n\) and \(y_{i+\frac{1}{2}} \in P_{n+1}\) for any integer \(i\).

First we give an expansion of the operator \((DU)^k\), which is analogous to Identity 3 and was known in [5]. It can be deduced algebraically by computing \((DU)^k\) as \(D (UD)^{k-1} U\), using Identity 3 with \(k\) replaced by \(k-1\), and the following equations \[D^l U = UD^l + rl U^{l-1}, \qquad \qquad DU^l =U^l D + rlU^{l-1}.\] Below we present a combinatorial argument that is similar to the proof of Identity 3 , which reveals the connection to set partitions.

Clearly Identity 3 follows from 7 . In fact, these two identities are equivalent.

Let \(t_k(x \rightarrow y)\) be the number of up-down alternating walks of length \(2k\) from \(x\) to \(y\), where \(x , y \in P_n\) for some \(n \in \mathbb{N}\). Similarly let \(t_{k+\frac{1}{2}}(x \rightarrow y)\) be the number of such walks of odd length \(2k+1\) from \(x \in P_n\) to \(y \in P_{n+1}\). We obtain the following analogous results of 2 and 2.

2.3 Another application of Theorem 1↩︎

Another fundamental identity proved in [1] for vacillating tableaux is \[\begin{align} \label{Eq:extra} B_{2k} = \sum_{\lambda \vdash n} ( m_k(\lambda))^2 = m_{2k}((n)), \qquad \text{for } n \geq 2k, \end{align}\tag{10}\] where \(B_m\) is the \(m\)-th Bell number that counts all set partitions of \([n]\). Similar identities involving sums of products of counts of simplified vacillating tableauxand their combinatorial interpretations are discussed in [10] and [2]. In this subsection we extend Identity 10 to differential posets. Let \(x, z \in P_n\) and \(k=k_1+k_2\) with \(k_1, k_2 \in \mathbb{N}\). Clearly \[m_k(x \rightarrow z) = \sum_{y \in P_n} m_{k_1}(x \rightarrow y) m_{k_2}(y \rightarrow z).\] In particular, when \(x=z\), after reversing the walks from \(y\) to \(z\), we have \[\sum_{y \in P_n } m_{k_1}(x \rightarrow y) m_{k_2} (x \rightarrow y) = m_k(x\rightarrow x)=\langle (UD)^k x, x\rangle.\] Then we can apply Identity 3 .

If \(e(x)=1\), then \(U^lD^l x =x\) for \(l \leq n\), and \(U^lD^l=0\) otherwise. For such an \(x\), we have \[m_k(x\rightarrow x)= \sum_{y \in P_n } m_{k_1}(x \rightarrow y) m_{k_2} (x \rightarrow y) = \sum_{l=1}^n r^{k-l}S(k,l).\] This happens when \(x=(n)\) or \((1^n)\) in Young’s lattice \(\mathbb{Y}\), or the element \(11\cdots 1\) in the Fibonacci differential poset \(Z(1)\). In particular, the above equation generalizes an identity of Martin and Rollet [11], corresponding to the case \(x=(n)\) in \(\mathbb{Y}\), for which Krattenthaler [3] provided a bijective proof. If in addition, \(n \geq k\), we obtain \[\sum_{y \in P_n } m_{k_1}(x \rightarrow y) m_{k_2} (x \rightarrow y) = \sum_{l=1}^k r^{k-l} S(k,l) = B_k(r),\] where \(B_k(r)\) is the number of \(r\)-colored set partitions on \([k]\). Here, an \(r\)-colored set partition of \([k]\) is a pair \(\Lambda=(\pi, \varphi)\), consisting of a set partition \(\pi\) of \([k]\) with a map \(\varphi: \mathrm{Arc}(\pi) \rightarrow [r]\) labeling its arcs. Identity 10 is the special case with \(k_1=k_2\) and \(x=(n)\geq 2k_1\) in \(\mathbb{Y}\).

The general case for \(r\)-differential posets is given by the following theorem.

We remark that Identity 3 can also be used to obtain explicit formulas for special \(m_k(\mu \rightarrow \lambda)\) in Young’s lattice when \(e(y, x)\) is easy to compute. Examples include Formulas (1.5) and (1.6) in [3] and the results in Section 4 of [12].

3 Algorithmic Bijections in Young’s Lattice↩︎

The \(r\)-th powers of Young’s lattice, \(\mathbb{Y}^r\), are typical examples of \(r\)-differential posets and bear special significance in algebraic combinatorics and representation theory. In the next two sections we present algorithmic bijections for the identities in Section 2 in the case \(P=\mathbb{Y}^r\). We begin with the case \(r=1\).

When \(P=\mathbb{Y}\) and \(x=\mu\) is a shape of size \(n\), we have \(e(\mu)=f^\mu\), and Identities 4 , 6 , 8 and 9 become \[\begin{align} \label{eq:Young1} n^k f^\mu &=& \sum_{\lambda \vdash n} m_k(\mu \rightarrow \lambda) f^\lambda = \sum_{\lambda \vdash n-1} m_{k+\frac{1}{2}} (\mu\rightarrow \lambda) f^\lambda, \end{align}\tag{11}\] \[\begin{align} \tag{12} (n+1)^k f^\mu = \sum_{\lambda\vdash n} t_{k}(\mu \rightarrow\lambda) \;f^\lambda = \sum_{\lambda \vdash n+1} t_{k-\frac{1}{2}}(\mu \rightarrow\lambda) \;f^\lambda , \tag{13} \end{align}\] where \(m_k(\mu \rightarrow \lambda)\) and \(m_{k+\frac{1}{2}}(\mu \rightarrow \lambda)\) count vacillating tableaux from \(\mu\) to \(\lambda\) with down-up alternating steps, while \(t_k(\mu \rightarrow \lambda)\) and \(t_{k+\frac{1}{2}}(\mu \rightarrow \lambda)\) count those with up-down alternating steps.

Halverson and Lewandowski gave a bijective proof of Identity 1 based on a deletion-insertion process, in which the deletion step uses jeu de taquin and the insertion step is given by RSK row insertion. In this section, we present a simpler deletion–insertion process that avoids the use of jeu de taquin. We then apply this new process to obtain bijective proofs of 11 and 12 .

We assume that the reader is familiar with the basic definition of RSK insertion on a partial tableau, which is a filling of some shape \(\lambda\) using distinct integers such that the entries are increasing along each row and each column. A partial tableau is standard if the set of entries is exactly \([n]\), where \(n=|\lambda|\).

The main step of our bijection is the lifted insertion, which inserts an integer \(i \in [n+1]\) into a SYT \(T\) of size \(n\) and yields a STY \(S\) of size \(n+1\).

Lifted insertion: Input: a SYT \(T\) of size \(n\) and an integer \(i\) with \(i \in [n+1]\),

1. (Lift): increase every entry \(j\) of \(T\) satisfying \(j \geq i\) by 1;

2. (Insert): insert \(i\) to the tableau obtained in step 1 via RSK row insertion.

The output is the SYT \(S\).

4 Deletion-insertion in powers of Young’s lattice↩︎

In this section we extend the deletion-insertion algorithm of Section 3 to \(\mathbb{Y}^r\) for \(r \geq 2\) and present bijective proofs for Identities 4 6 and 8 9 .

Elements in \(\mathbb{Y}^r\) are \(r\)-tuples \(\Lambda= (\lambda^{(1)}, \dots, \lambda^{(r)})\) of integer partitions ordered coordinate-wise by inclusion. The minimal element \(\hat{0}\) of \(\mathbb{Y}^r\) is \((\emptyset, \cdots, \emptyset)\), and \(\Lambda\) is of rank \(n\) if and only if \(|\lambda^{(1)}| + \cdots + |\lambda^{(r)}|=n\). In addition, \(\Lambda=(\lambda^{(1)}, \dots, \lambda^{(r)})\) covers \(\Theta=(\mu^{(1)}, \mu^{(2)}, \dots, \mu^{(r)})\) if and only if \(\lambda^{(j)}=\mu^{(j)}\) for all but one \(j \in [r]\), and for the exceptional index \(j\), \(\lambda^{(j)} \supset \mu^{(j)}\) and \(|\lambda^{(j)} / \mu^{(j)}|=1\).

Assume \(\Lambda=(\lambda^{(1)}, \dots, \lambda^{(r)})\) is of rank \(n\). Let \(a_i=|\lambda^{(i)}|\). Then a saturated chain from \(\hat{0}\) to \(\Lambda\) can be represented by a sequence of partial tableaux \((T^{(1)}, \cdots, T^{(r)})\), where \(T^{(i)}\) is of shape \(\lambda^{(i)}\), and the set of all entries in \(T^{(1)}, \cdots, T^{(r)}\) is exactly \([n]\).

Let \(\mathcal{E}(\Lambda)\) be the set of saturated chains from \(\hat{0}\) to \(\Lambda\). It follows that \(e(\Lambda) =|\mathcal{E}(\Lambda)|= \binom{n}{a_1, \dots, a_r} \prod_i f^{\lambda^{(i)}}.\) Let \(\Theta, \Lambda \in \mathbb{Y}^r\). Following the notations in Section 3, we again use \(\mathcal{VT}_i(\Theta \rightarrow \Lambda)\) to represent the set of down-up alternating walks from \(\Theta\) to \(\Lambda\) of length \(2i\), and \(\mathcal{VT}^\uparrow_i(\Theta \rightarrow \Lambda)\)for the set of up-down ones.

For a fixed positive integer \(r\), let \(r[n]=[n]\times [r]\). We interpret each pair \((i, c) \in r[n]\) as the integer \(i\) with color \(c\).

5 Final Remarks↩︎

We finish this paper with some remarks.

5.1 The deletion procedure↩︎

The main ingredients of the bijections in this paper are the deletion procedure and (lifted) RSK row insertion. RSK insertion has the useful property that if a tableau \(S\) is obtained from a partial tableau \(T\) by inserting \(i\), then \(i\) and \(T\) can be recovered uniquely from \(S\) together with the shape of \(T\). Therefore, for the deletion procedure, it suffices to have an operation with the following property: whenever a tableau \(T\) is obtained from a tableau \(S\) by deleting \(i\), one can recover \(S\) uniquely from \(T\), \(i\), and the shape of \(S\).

The deletion procedure used in this paper is the simplest possible choice: delete the maximal entry of \(S\).

The bijection \(\phi_n^k\) constructed in the proof of Identity 11 can also be described in terms of growth diagrams. It is essentially equivalent to the bijection given by Krattenthaler in [3]. The only difference is that the integer sequence \(\boldsymbol{i}\) used in [3] appears in reversed order relative to the sequence associated with \(\phi_n^k\). For example, let \(\mu=(3,2,1)\) and \(\lambda=(2,2,1,1)\). Following [3], take the followng SYT \(P\) of shape \(\lambda\) and vacillating tableau \(\Gamma\) from \(\mu\) to \(\lambda\)³: \[P= \ytableausetup{smalltableaux} \begin{ytableau} 1 &2 \\ 3 & 5 \\ 4 \\ 6 \end{ytableau}, \quad \Gamma= \ytableausetup{boxsize=7pt} \left(\ydiagram{3,2,1},\;\ydiagram{2,2,1,}, \;\ydiagram{2,2,2},\;\ydiagram{2,2,1}, \;\ydiagram{2,2,2}, \;\ydiagram{2,2,1}, \;\ydiagram{2,2,1,1} \right).\]

Under our map \(\phi_n^k\) the pair \((P, \Gamma) \in \mathcal{SYT}(\lambda) \times \mathcal{VT}_3(\mu \rightarrow \lambda)\) corresponds to the pair \((T, (3,2,2))\), while the bijection in [3] maps \((P, \Gamma)\) to \((T, (2,2,3))\), where \[T= \ytableausetup{smalltableaux} \begin{ytableau} 1 & 4 & 6 \\ 2 & 5 \\ 3 \end{ytableau}.\] Our bijection \(\phi_n^k\) provides a more concise description of the growth-diagram bijection in [3]. Krattenthaler considered permutation fillings of a Ferrers diagram with \(n+k\) rows whose lengths, from top to bottom, are \(n, n+1, \dots, n+k, \dots, n+k\), where \(n+k\) occurs \(n\) times. In fact, it suffices to consider only the first \(k\) rows, whose lengths are \(n, n+1, \dots, n+k-1\). See Figure 1 for an illustration. In the figure we keep the same notations as in [3] and align the squares for the growth diagram at the lower-left corner.

Label all the vertices along the left boundary with empty partitions. Then the bijection \(\phi_n^k\) asserts that the following two sets of data determine the same growth diagram:

1. The sequence of partitions along the top boundary, corresponding to a tableau \(P \in \mathcal{SYT}(\lambda)\), together with the sequence of partitions along the right boundary, corresponding to a vacillating tableau \(\Gamma\) from \(\lambda\) to \(\mu\);

2. A restricted filling of the Ferrers diagram, corresponding to a sequence \(\boldsymbol{i} \in [n]^k\), and the sequence of distinct partitions along the bottom boundary, corresponding to a tableau \(T \in \mathcal{SYT}(\mu)\). The filling is restricted in the sense that each row contains exactly one cross and no two crosses occupy the same column. Moreover, two consecutive partitions along the bottom boundary differ by one square if and only if the column immediately above them contains no cross.

There are other choices for the deletion procedure. Halverson and Lewandowski used jeu de taquin to remove the entry \(i_j\) in the \(j\)-th step of the algorithm. Another natural alternative is to delete the minimal element, or the \(t\)-th element for a prefixed \(t\) in \([n]\), in a partial tableau again using jeu de taquin. It would be interesting to understand the combinatorial significance of these and other deletion procedures, and to investigate how different choices affect the resulting bijections.

5.2 Rim Hook Lattice↩︎

Another model of \(r\)-differential posets is the \(r\)-rim hook lattice. A rim hook is a set of squares forming a contiguous strip with at most one square on each diagonal. An \(r\)-rim hook is a rim hook containing exactly \(r\) squares.

For two integer partitions \(\mu\) and \(\lambda\), if \(\mu \subset \lambda\) and \(\lambda \setminus \mu\) is an \(r\)-rim hook, then we say that \(\mu \lessdot \lambda\). Equivalently, \(\mu \lessdot \lambda\) if \(\mu\) can be obtained from \(\lambda\) by removing an \(r\)-rim hook. We define \(\mu \preceq \lambda\) if \(\mu\) can be obtained from \(\lambda\) by successively removing \(r\)-rim hooks.

Let \(RH_r\) be the set of integer partitions \(\lambda\) such that \[\emptyset \preceq \lambda.\] Fomin and Stanton [13] proved that \(RH_r\) is a lattice and is isomorphic to \(\mathbb{Y}^r\). Hence the bijections in Section 4 naturally extend to \(RH_r\).

Nevertheless, we can consider alternating walks directly on the Hasse diagram of \(RH_r\) and construct deletion-insertion algorithms using a rim hook version of the jeu de taquin together with the rim hook insertion algorithm; both are developed by Stanton and White [14], [15].

To get a set with cardinality \(rn\), instead of integers in \([n]\) with \(r\) colors, one uses the set of hook tableaux of size \(r\) and content \(i \in [n]\). Here, a hook tableau of size \(r\) is a tableau of shape \((i, 1^{r-i})\) whose entries are all equal, and this common value is called the content. The rim hook insertion algorithm developed by Stanton and White allows one to insert a hook tableau of size \(r\) with content \(i\) into an \(r\)-rim hook tableau \(P\) with no entry \(i\). This algorithm can be inverted, in a similar way that one inverts RSK row insertion.

Combinatorially, walks in \(\mathbb{Y}^r\) and \(RH_r\) lead to two different representations of \(r\)-colored discrete structures, therefore provide distinct perspectives on their combinatorial properties. For example, Chen and Guo [16] studied colored matchings via oscillating rim hook tableaux and oscillating tableaux in \(\mathbb{Y}^2\), that is, walks from \(\hat{0}\) to \(\hat{0}\) consisting of up and down steps that are not necessarily alternating.

5.3 Representation Interpretations↩︎

Identity 1 arises from the representation theory of partition algebras \(\mathbb{C}A_k(n)\), reflecting the Schur-Weyl duality between the symmetric group \(S_n\) and \(\mathbb{C}A_k(n)\) on the \(k\)-fold tensor power \(M_n^{\otimes k}\) of the permutation module \(M_n\) of \(S_n\); see [1]. This duality has been further developed in [17], [18]. Identities 11 and 13 exhibit a strong similarity to Identity 1 , and rim hook tableaux are closely related to the wreath product \(S_m[Z_k]\), in particular, the hyperoctahedral group (the signed permutation group). Hence it would be interesting to provide representation-theoretic interpretations for the new identities proved in the present paper.

References↩︎