Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers 2

up vote 8 down vote accepted

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.

share|improve this answer
    
Thank you! (And welcome to MO.) –  darij grinberg Apr 29 '13 at 18:53
add comment

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?)

share|improve this answer
    
Thanks for this -- I guess we should discuss this if there's a preseminar meeting on Wednesday. –  darij grinberg Apr 30 '13 at 2:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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