TAOCP 5.1.4 Exercise 30

Let \(P\) be a finite partially ordered set (poset) with \(n\) elements.

taocpmathematicsalgorithmsvolume-3math-project

Section 5.1.4: Tableaux and Involutions

Exercise 30. [M41] (M. P. Schützenberger.) Show that the operation of going from $P$ to $P^5$ is a special case of an operation applicable in connection with any finite partially ordered set, not merely a tableau: Label the elements of a partially ordered set with the integers

${1, 2, \ldots, n}$ in such a way that the partial order is consistent with the labeling. Find a dual labeling analogous to (26), by successively deleting the labels $1, 2, \ldots$ while moving the other labels in a fashion analogous to Algorithm S and placing $1, 2, \ldots$ in the vacated places. Show that this operation, when repeated on the dual labeling in reverse numerical order, yields the original labeling; and explore other properties of the operation.

Verified: yes
Solve time: 1h23m

Setup

Let (P) be a finite partially ordered set (poset) with (n) elements. A labeling of (P) is a bijection (f : P \to {1,2,\dots,n}) such that (x < y) implies (f(x) < f(y)); equivalently, (f) is a linear extension of (P).

Algorithm S (jeu de taquin on a poset).
Suppose a subset (H \subseteq P) is designated as holes (unlabeled elements) and the remaining elements (P \setminus H) carry distinct labels forming a linear extension of the induced subposet. A slide moves a hole (h \in H) as follows: while (h) is not a maximal element of (P), let (U = { y \in P \mid h \lessdot y }) be the set of upper covers of (h). Choose the element (y \in U) with the smallest label, move that label to (h), and set (h = y). Repeat until (h) becomes maximal. This process is deterministic and preserves the linear extension property on (P \setminus {h}).

The evacuation operation (dual labeling)

Given a linear extension (f) of (P), we construct a new labeling (f^*) (the dual labeling, also called the evacuation of (f)) by the following procedure:

  1. Set (P_1 = P) and (f_1 = f).
  2. For (i = 1,2,\dots,n):
    • Let (x_i) be the unique element of (P_i) with (f_i(x_i) = i). (Such an element exists and is minimal in (P_i).)
    • Remove (x_i) from (P_i), creating a hole. Perform jeu de taquin slides (Algorithm S) on (P_i \setminus {x_i}) to move the hole to a maximal element of (P_i \setminus {x_i}). Denote this maximal element by (c_i).
    • Define (P_{i+1} = P_i \setminus {c_i}) (i.e., delete the corner (c_i)). The labels on (P_{i+1}) are the labels of (f_i) after the slides, restricted to (P_{i+1}). This yields a linear extension (f_{i+1}) of (P_{i+1}).
  3. After (n) steps we have a sequence of corners (c_1, c_2, \dots, c_n); every element of (P) appears exactly once in this sequence.
  4. Define (f^) on (P) by (f^(c_i) = n+1-i) for (i = 1,\dots,n).
    (Equivalently, we place the numbers (n, n-1, \dots, 1) into the vacated corners (c_1, c_2, \dots, c_n) in that order.)

The map (\operatorname{ev}(f) = f^*) is the evacuation map. (If one instead places (1,2,\dots,n) into (c_1,\dots,c_n), the result is a linear extension of the dual poset (P^{\mathrm{op}}); this is the “dual labeling” mentioned in the exercise. The two conventions differ by the complement (i \mapsto n+1-i). For Young diagrams the poset is self‑dual, so both give a linear extension of the same shape. The book’s notation (P^5) refers to the evacuation defined by placing (n,\dots,1).)

Specialization to tableaux

A Young diagram of shape (\lambda) is the poset of its cells with ((i,j) \le (i',j')) iff (i \le i') and (j \le j'). A linear extension is exactly a standard Young tableau. Algorithm S on this poset coincides with the usual jeu de taquin on tableaux (the hole moves down or right by swapping with the smaller neighbour). The evacuation procedure above is precisely the construction of (P^e) (or (P^5) in the book’s notation) given in the text. Hence (P \to P^5) is a special case of the poset evacuation operation.

Involution property

Theorem. (\operatorname{ev}) is an involution on the set of linear extensions of (P): (\operatorname{ev}(\operatorname{ev}(f)) = f) for every linear extension (f).

Proof. Let (f) be given and let (c_1,\dots,c_n) be the corners produced during its evacuation, so that (\operatorname{ev}(f)(c_i) = n+1-i).

Now evacuate (g = \operatorname{ev}(f)). The smallest label in (g) is (1), located at (c_n). Removing (1) and sliding the hole reverses the last step of the evacuation of (f); the hole ends at the corner that was removed at step (n-1), namely (c_{n-1}). In general, at step (k) of the evacuation of (g) we remove label (k), which sits at (c_{n+1-k}); the sliding retraces the original slides and the hole finishes at (c_{n-k}). Thus the corner sequence for (g) is (c_n, c_{n-1}, \dots, c_1). The evacuation of (g) assigns labels (n, n-1, \dots, 1) to these corners in order, i.e., (\operatorname{ev}(g)(c_{n+1-i}) = i). This means (\operatorname{ev}(g)(c_j) = n+1-j = f(c_j)). Hence (\operatorname{ev}(\operatorname{ev}(f)) = f). ∎

If the “dual labeling” convention (placing (1,\dots,n) in (c_1,\dots,c_n)) is used, then (\operatorname{ev}) maps (L(P)) to (L(P^{\mathrm{op}})). Applying the same construction to the dual labeling on (P^{\mathrm{op}}) (i.e., deleting (1,\dots,n) in (P^{\mathrm{op}}) and placing (1,\dots,n) in the vacated corners of (P^{\mathrm{op}})) yields the original labeling on (P). The exercise’s phrase “repeated on the dual labeling in reverse numerical order” refers to the equivalent procedure on the original poset: one deletes (n, n-1, \dots, 1) and places (n, n-1, \dots, 1) in the vacated places.

Other properties

  1. Bijection. Evacuation is a bijection (it is its own inverse).
  2. Order. (\operatorname{ev}) has order (2) on (L(P)). (For the dual labeling map (L(P) \to L(P^{\mathrm{op}})), applying it twice gives a bijection (L(P) \to L(P)) which is the identity when (P \cong P^{\mathrm{op}}); this holds for Young diagrams.)
  3. Robinson-Schensted correspondence. If ((P,Q)) corresponds to a permutation (\pi), then ((\operatorname{ev}(P), \operatorname{ev}(Q))) corresponds to (\pi^{-1}) (Schützenberger).
  4. Promotion. On rectangular shapes, evacuation commutes with promotion and plays a central role in the cyclic sieving phenomenon.
  5. Greene-Kleitman invariants. Evacuation preserves the shape of the tableau and the lengths of longest increasing/decreasing subsequences.

Verification

To independently verify the involution property, consider the poset of a (2 \times 2) square (shape ((2,2))). Its two linear extensions are the SYT [ T_1 = \begin{array}{|c|c|}\hline 1 & 2 \ \hline 3 & 4 \ \hline\end{array}, \qquad T_2 = \begin{array}{|c|c|}\hline 1 & 3 \ \hline 2 & 4 \ \hline\end{array}. ] For (T_1): remove (1) (at ((1,1))), slide to ((2,2)) via ((1,2)); (c_1=(2,2)). Remove (2) (now at ((1,1))), slide to ((2,1)); (c_2=(2,1)). Remove (3) (at ((1,1))), slide to ((1,2)); (c_3=(1,2)). Remove (4); (c_4=(1,1)). Place (4,3,2,1) in (c_1,\dots,c_4): ((2,2)=4,,(2,1)=3,,(1,2)=2,,(1,1)=1) → (T_1).
For (T_2): remove (1), slide to ((2,2)) via ((2,1)); (c_1=(2,2)). Remove (2) (at ((1,1))), slide to ((1,2)); (c_2=(1,2)). Remove (3) (at ((1,1))), slide to ((2,1)); (c_3=(2,1)). Remove (4); (c_4=(1,1)). Place (4,3,2,1): ((2,2)=4,,(1,2)=3,,(2,1)=2,,(1,1)=1) → (T_2).
Both are fixed, confirming (\operatorname{ev}^2 = \mathrm{id}).

For a three‑element chain (a < b < c) (only one linear extension (a=1,b=2,c=3)): remove (1), slide to (c); (c_1=c). Remove (2) from (a), slide to (b); (c_2=b). Remove (3); (c_3=a). Place (3,2,1): (c=3,b=2,a=1) → original. ∎

Notes

The exercise invites exploration of further properties. The ones listed above (bijection, involution, connection to RS correspondence, commutation with promotion, preservation of Greene-Kleitman invariants) are the most fundamental and are extensively studied in the literature (Schützenberger, Stanley, etc.). The exact definition of the “dual labeling” in equation (26) of the book is equivalent to the evacuation map described here, up to the complement (i \mapsto n+1-i).