Home » Mathematics » Algebraic combinatorics » Knuth Equivalence and Tableau Products

Knuth Equivalence and Tableau Products

I found (and still find) the ideas and algorithms around Young Tableaux to be fairly unintuitive: jeux de taquin (JDT), Knuth equivalence and rectification; the RSK correspondence; the Littlewood-Richardson rule(s); promotion and evacuation.

In this post, I want to state (without proof) the basic ideas and facts surrounding the first algorithm above, JDT, and its connection to Knuth equivalence. The reference I am using is Fulton’s Young Tableaux textbook, which covers almost all of the above-mentioned algorithms. For this post, I’m essentially restating section 3.1, and parts of sections 1 and 2.

Let’s begin.

Knuth equivalence is an algorithm (an equivalence relation) that provides a computational solution to the following problem, called the longest-disjoint-subwords problem. Suppose we have a word w from some (ordered) alphabet, say

w = 16312552

with the usual ordering. What is the longest alphabetical (i.e., nondecreasing) subword of w? That’s easy enough… it’s 11255, omitting the 6,3,5,2 letters. What if we’re allowed to form two separate (disjoint) words — what is the longest total word length we can get? That’s a bit harder, but in this case 7 letters is optimal (for instance: 1355;122 is one way to do it). And, with three or more words, we can get all eight letters.

The problem of finding the largest possible (total) length of n nondecreasing subwords is fairly tricky in general. For example, we couldn’t reuse the 11255 word when we were looking for pairs of words; we had to break it up. There are a large, combinatorial number of possibilities to check, so we can’t check all of them.

This is where Knuth equivalence comes in. We introduce two elementary transformations that bump a letter to the left in the word, while preserving the answer to the above question. These transformations are:

\text{if}\ x < y \leq z: \text{ we can do } yzx \leftrightarrow yxz

and

\text{if}\ z \leq y < x: \text{ we can do } zxy \leftrightarrow xzy.

Focus on the letter x, which moves leftwards in each of the above transformations. (The idea is, roughly, to keep moving low numbers to the left.) We say two words w and w' are Knuth equivalent if we can get from one to the other using a sequence of these moves and their inverses.

It’s not at all obvious what kind of properties, if any, this equivalence relation has. The key one is the following:

Proposition. Let w and w' be words, and let \ell (resp. \ell') be the largest total lengths obtained using k disjoint, alphabetical subwords of w (respectively w'). If w and w' are Knuth equivalent, then \ell = \ell'.
Proof. Check all the cases. (It suffices to consider the case where w' and w are precisely one elementary transformation apart, and to just show one inequality, say \ell \leq \ell'.)

So, thanks to a careful analysis of the inequalities, we have a way of manipulating our words without affecting the solutions to the longest-disjoint-subwords problem. (Note: in one of the cases of the above proof, the words actually change when we apply these transformations. But the total lengths remain the same.)

At this point, a reasonable question to ask is, what sort of ‘canonical’ form can we get by applying these transformations over and over? Can we get one that makes it easy to read off the answer to the problem? This leads to the second key input: Young Tableaux (and Young diagrams).

Definition. A partition is a finite weakly decreasing sequence of positive integers, say \lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0). A Young diagram is a pictorial representation of a partition, as a grid of left-aligned boxes, with \lambda_1 boxes in the first row, \lambda_2 in the second, and so on.

Definition. A Young Tableau is a Young diagram with positive integers entered in the boxes, nondecreasing in both the rows and columns. A semi-standard or column-strict Young Tableau is one where the columns are strictly increasing.

Semi-Standard Young Tableaux (SSYTs for short) are perfect for the longest-disjoint-subwords problem. For one thing:

Proposition. Any word w is Knuth equivalent to the row word of a unique(!) SSYT.

Let’s write out the entries of our tableau, from left to right, shortest row to longest row:

\text{row}(T) = 63511225.

Compare this to the visualization of the tableau itself. Any alphabetical subword of row(T) must follow a path from left to right across the tableau. It can go upwards diagonally too, but not vertically upwards (since the columns are strict).

So, right away we see that the longest possible word has length equal to the number of columns in the tableau, that is, the length of the first (longest) row. Likewise, if we’re allowed two words, the best we can do is the sum of the lengths of the first and second rows. And so on.

Proposition. The solutions to the longest-disjoint-subwords problems for the row word of an SSYT T of shape \lambda are, for each k, the sum \lambda_1 + \cdots + \lambda_k.

This concludes the theoretical discussion of the problem. To summarize: given a word w, there exists a unique semi-standard Young tableau T, whose row word row(T) is obtained by applying the elementary Knuth transformations to w, and which has the same answers to the longest-disjoint-subwords problem. But now these answers are easy to observe.

For fun: since concatenation of strings is associative, we get the following product structure on the set of tableaux:

Definition. Let T,U be semi-standard Young tableaux. We define the product tableau T \cdot U to be the (unique) tableau corresponding to the concatenated word row(T) \cdotrow(U).

This operation is automatically associative, and its identity element is the “empty tableau”. Since associativity is typically the most difficult property to establish in algebra (after well-definedness), this is something of a Big Deal, and we’ll return to this product structure later.

The last thing I’d like to do is talk about bumping and sliding (JDT), two algorithms that carry out the above tableau product / Knuth equivalence procedures.

Bumping!
Given a tableau T, let’s say we want to multiply on the right by a single block, x. That is, we want to simplify the word row(T)\cdot x. Well, here’s an algorithm to do so, phrased in terms of the tableau:
1. Move x backwards along the first row from right to left. As soon as you encounter something \leq x, stop and ‘bump out’ the last (> x) box you passed, replacing it by x. (If x is placed on the end of the row, there’s nothing to bump, so the algorithm is completed.)
2. Repeat step 1 on the subsequent row, using the bumped-out value. Repeat until completed.

Great!

Lemma (Easy). The result is an SSYT.
Lemma (Hard). The row bumping algorithm preserves Knuth equivalence.

In other words (since the output is a new tableau), row bumping computes the tableau product, at least for a single box. To compute a more complicated product, T \cdot U, look at the concatenation row(T) \cdotrow(U) and use the row bumping algorithm iteratively. Pictorially, this corresponds to bumping in the boxes of U, one by one from left to right, starting with the shortest row.

Sliding and Rectification!
These algorithms start with skew tableaux. A skew diagram is a Young diagram with a smaller Young diagram deleted from it. All the other definitions (skew tableau, column-strict, row word, etc) work accordingly.

Here’s an algorithm, called sliding or jeu de taquin (JDT), to convert an arbitrary skew SSYT to a normal SSYT:

  1. Pick any inside corner, that is, a square in the deleted area, but such that both the squares below and to the right are both occupied.
  2. ‘Fill the hole’ by moving the smaller of the two entries (from the squares below or to the right) into it. In the case of a tie, choose the square below.
  3. Repeat step 2 at the new ‘hole’. Keep repeating until both the square below and the square to the right are empty.
  4. Repeat steps 1-3, starting at another inside corner, until the deleted area is all filled.

Lemma (Easy). The result, called the rectification, is an SSYT.
Lemma (Hard). Sliding/JDT (specifically, step 2) preserves Knuth equivalence. That is, if T is the original skew SSYT and T' is its rectification, then row(T) is Knuth equivalent to row(T').

Why is this helpful? Well, it’s really easy to express row(T) \cdotrow(U) in terms of skew shapes: just put T, as a whole, below and to the left of U, touching at the tip. This is a skew tableau, called T * U, and its row word is row(T) \cdotrow(U). Consequently, its rectification must be the tableau T \cdot U.

So, now we have two algorithms that convert arbitrary words w into the row word of a tableau, while respecting Knuth equivalence. Although I’ve phrased this entire post as though the goal was to solve the longest-disjoint-subwords problem, the real reason I care about it is for the tableau product structure, which is of important use in Schubert calculus. But that’s another post.

Advertisements

1 Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: