11
$\begingroup$

Schützenberger promotion, studied (for example) in Richard Stanley, Promotion and Evacuation, 2009, is a permutation of the set of all linear extensions of a finite poset. Since one can identify the linear extensions of a poset with saturated chains of order ideals in that poset, this allows one to also view Schützenberger promotion as a permutation of the set of the latter. The famous promotion of standard Young tableaux is a particular case of this.

Striker-Williams promotion, defined in Jessica Striker, Nathan Williams, Promotion and Rowmotion, arXiv:1108.1172v3, Definition 4.13, is a permutation of the set of all order ideals (not saturated chains of order ideals!) of a so-called "rc poset" (which is a poset with a map into $\mathbb Z^2$ satisfying certain conditions, best viewed as a way to draw its Hasse diagram on a grid; see below or §4.2 of Striker-Williams for an exact definition).

Apparently people are considering these two promotions to be closely related. However, the only direct relation I am aware of is Striker-Williams Theorem 4.12, which bijects Schützenberger promotion on standard tableaux on a two-rowed Young diagram with Striker-Williams promotion on a poset which looks like a triangle grid.

Questions:

1. Is this really the only relation? Is promotion of standard Young tableaux of a Young diagram with more than $2$ rows not a (known) case of Striker-Williams promotion?

2. I've seen some kind of promotion on semistandard Young tableaux being mentioned on the internet. Assuming it's not a typo, how is that defined?


Appendix:

Let me define the two notions involved for the sake of completeness. Probably the sources quoted give better definitions...

Definition of Schützenberger promotion: Let $P$ be a finite poset. Let $\mathcal L\left(P\right)$ denote the set of all linear extensions of $P$. We define a map $\partial : \mathcal L\left(P\right)\to \mathcal L\left(P\right)$ as follows:

Let $f \in \mathcal L\left(P\right)$ be a linear extension. We set $p=\left|P\right|$, and we view $f$ as a function $P\to\left\lbrace 1,2,...,p\right\rbrace$, i. e., as a labelling of the elements of $P$ by the numbers $1$, $2$, ..., $p$ (we get this labelling by labelling every element $v\in P$ with the number $\left| \left\lbrace w\in P \ \mid \ f\left(w\right)\leq f\left(v\right) \right\rbrace \right|$). Define a (dynamic) map $g:P\to\mathbb Z$ by $g = f$ (we will be modifying $g$, while $f$ remains static). If $p=0$, do nothing. Else, set $u$ to be the element of $P$ labelled $1$ (that is, the smallest element of $P$ with respect to $g$), and do the following loop:

While there exists an element of $P$ covering $u$:

let $v$ be the smallest (with respect to $g$) among the elements of $P$ covering $u$ (that is, the element $p$ of $P$ covering $u$ with smallest $g\left(p\right)$);

slid the label of $v$ down to $u$ (that is, set $g\left(u\right)$ to be $g\left(v\right)$, accepting that $g$ will temporarily fail to be injective);

set $u = v$.

Endwhile.

After the end of this loop, label $u$ with $p+1$ (that is, set $g\left(u\right) = p+1$), and then subtract $1$ from each label (i. e., replace $g$ by $g-\mathbf{1}$, where $\mathbf{1}$ is the constant function $P\to\mathbb Z,\ p\mapsto 1$).

The resulting $g$ is called the promotion of $f$, and denoted by $\partial f$. (It is more common to call it $f\partial$, so that $\partial$ is seen as a map acting from the right).

Definition of Striker-Williams promotion: Let $P$ be a finite poset. Let $J\left(P\right)$ denote the set of all order ideals of $P$. For every $q\in P$, define a map $t_p : J\left(P\right) \to J\left(P\right)$ as follows: Let $I \in J\left(P\right)$. If $I \bigtriangleup \left\lbrace p\right\rbrace$ (with $\bigtriangleup$ standing for "symmetric difference") is an order ideal of $P$, set $t_p\left(I\right) = I \bigtriangleup \left\lbrace p\right\rbrace$. Otherwise, set $t_p\left(I\right) = I$.

Let $\mathbb Z^2_{\operatorname*{ev}}$ denote the $\mathbb Z$-submodule of $\mathbb Z^2$ spanned by $\left(1,1\right)$ and $\left(2,0\right)$. In other words, let $\mathbb Z^2_{\operatorname*{ev}}$ be the set of all $\left(x,y\right)\in\mathbb Z^2$ for which $x+y$ is even.

Now, let $P$ be a finite rc-poset; this means a poset along with a map $\pi : P \to \mathbb Z^2_{\operatorname*{ev}}$ such that whenever an element $p_1$ of $P$ covers an element $p_2$ of $P$, we have $\pi\left(p_1\right)-\pi\left(p_2\right) \in \left\lbrace \left(-1,1\right), \left(1,1\right) \right\rbrace$. (See §4.2 of Striker-Williams for some good pictures of what this means.)

For every $p\in P$, let $\pi_1\left(p\right)$ denote the first coordinate of $\pi\left(P\right)$. Now, consider the composition of the maps $t_p$ in decreasing order of $\pi_1\left(p\right)$ (the relative order of the $t_p$ for distinct $p$ having the same $\pi_1\left(p\right)$ does not matter). This composition is Striker-Williams promotion.

$\endgroup$

2 Answers 2

12
$\begingroup$

When a tableau has two rows (of any length, skew is ok), there is a nice bijection between linear extensions on the poset defined by the shape of the tableau and order ideals on another related poset. This is what Theorem 4.12 in Promotion and Rowmotion says. Once we move to three rowed tableaux, though, it's not so clear how to biject from linear extensions on the shape to order ideals on some other poset. It would be great to find other situations where these notions coincide, so if there are some posets whose number of order ideals equals the number of SYT of a certain shape, it would be good to test if the notions are equivalent. I did check whether promotion on the order ideals that are in bijection with SSYT of staircase shape is the same as promotion on those SSYT directly, and unfortunately, the notions do not coincide. (I believe promotion on SSYT of a fixed shape with entries at most n can be defined in the same way as for SYT, though I can't find a reference at the moment. Delete all the 1's and do jeu-de-taqin, then decrement every entry and fill in the rest of the shape with n's.)

So, to summarize, promotion on order ideals is different than promotion on linear extensions except in special cases where we have a correspondence between linear extensions on the shape of the tableaux and order ideals in a related poset.

$\endgroup$
1
  • $\begingroup$ Jessica and I discussed our respective approaches in person yesterday, and we feel that they're quite different. Jessica's answer treats standard tableaux; my answer (which appears below) treats semistandard tableaux. Her tableaux have only two rows; mine can have any number of rows. Her tableaux can be skew; mine must be non-skew, and indeed must be rectangular. She associates tableaux with order ideals in subposets of root posets of type A (triangles); I associate tableaux with points in the order polytope of minuscule posets of type A (rectangles). $\endgroup$ Mar 21, 2015 at 15:08
5
$\begingroup$

Regarding your first question, promotion of standard Young tableaux of rectangular shape (with any number of rows) can be viewed as as a special case of the piecewise-linear "lift" of Striker-Williams promotion. Specifically, there is an equivariant bijection between (on the one hand) the action of the Schutzenberger promotion operator on the set of semistandard Young tableaux of rectangular shape with $A$ rows and $B$ columns having entries between 1 and $n$, and (on the other hand) the action of the piecewise-linear promotion operator on the rational points in the (reverse) order polytope ${\cal O}(([A] \times [n-A])^{\rm op})$ with denominator dividing $B$. See http://jamespropp.org/gtt-promotion.txt for a more detailed and in-depth explanation.

Regarding your second question, my understanding is that there are two equivalent definitions of promotion for semistandard tableaux, one using jeu de taquin (which I don't really understand) and the other using Bender-Knuth involutions. I could say more about the latter (and will if you like), but maybe that's enough for now. One early reference for this is E. Gansner, On the equality of two plane partition correspondences, Discrete Math. 30 (1980), 121-132. (Can anyone suggest anything more recent?)

$\endgroup$
1
  • $\begingroup$ Thanks for this -- I guess we should discuss this if there's a preseminar meeting on Wednesday. $\endgroup$ Apr 30, 2013 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.