« The induced representation
The cyclotomic identity and Lyndon words »

Young’s lattice

November 2, 2009

As we saw last time, a sequence of nested groups gives rise to a graded “poset” in which objects can be related by more than one arrow. The poset we want to construct now is given by the sequence S_0 \le S_1 < S_2 < S_3 of symmetric groups (where S_0 and S_1 are both the trivial group). Since irreducible representations of the symmetric groups are parameterized by Young diagrams, this gives the set of Young diagrams a graded structure where the elements of rank n are the Young diagrams with n boxes.

It turns out that this “poset” is a genuine poset; in other words, in the restriction of an irreducible representation of S_n to an irreducible representation of S_{n-1}, the resulting representation contains each irreducible representation at most once. In fact, much more is true. In a poset we write \lambda \triangleright \mu if \lambda > \mu and there is no \lambda' with \lambda > \lambda' > \mu; this relation is called covering. So elements of rank n cover elements of rank n-1.

Theorem (Branching Rule): \lambda \triangleright \mu if and only if \mu is obtained from \lambda by removing a box.

This is the remarkable theorem that really justifies the choice of Young diagrams as a natural description of the irreducible representations of the symmetric group. Today we’ll explore some of the consequences of this theorem.

Let L_n denote the rank of order n, where L_0 contains only the empty partition \emptyset. Let \mathbb{C}[L] denote the free vector space on L, which is graded by rank, hence

\displaystyle \mathbb{C}[L] \simeq \bigoplus_{n=0}^{\infty} \mathbb{C}[L_n].

We can think of elements of \mathbb{C}[L_n] as generalizing direct sums of irreducible representations of S_n. From this perspective, \mathbb{C}[L] comes equipped with two distinguished linear operators U, D such that

\displaystyle U \lambda = \sum_{\mu \triangleright \lambda} \mu

and

\displaystyle D \lambda = \sum_{\lambda \triangleright \mu} \mu.

U, D restrict to operators U : \mathbb{C}[L_n] \to \mathbb{C}[L_{n+1}] and D : \mathbb{C}[L_{n+1}] \to \mathbb{C}[L_n] and are essentially the induction and restriction maps. Of course, these maps (which one can refer to as “up” and “down,” respectively) can be defined for any graded poset, but part of the reason we like Young’s lattice is that its up and down operators carry special significance. Frobenius reciprocity is visible in the statement that U = D^T.

The differential property

The operators U, D have a surprising property whose significance was first recognized by Stanley in 1988 (!).

Proposition: DU - UD = I.

Proof. Suppose a Young diagram \lambda has k boxes on its southeast boundary. If we add a box and then remove a second box, we could also have removed the second box and added the first box, so these terms in DU - UD cancel. If we add and remove the same box, there are k+1 ways to do this. However, if we remove and add the same box, there are k ways to do this. Hence (DU - UD) \lambda = \lambda as desired.

Note that this is essentially the same balls-in-bags argument as in the previous post and establishes the following remarkable fact.

Fact: The action of U, D on \mathbb{C}[L] is a representation of the Weyl algebra.

I asked what this means over at MathOverflow, but Ben Webster’s reply was a little over my head. (If somebody wants to add their own answer, that would be great!) Posets with this property are called 1-differential because D behaves like \frac{\partial}{\partial U}; see Stanley’s paper for more discussion.

The upshot of all of this is that polynomials in D, U can be written as a unique linear combination of terms of the form U^a D^b by repeated application of the above relation. This is immensely useful for counting walks on Young’s lattice, which correspond to interesting combinatorial information about tableaux. For example,

\displaystyle U^n \emptyset = \sum_{\lambda \vdash n} f^{\lambda} \lambda

because a Young tableaux of shape \lambda is precisely a sequence of ways to build the corresponding Young diagram by adding boxes. (Thus f^{\lambda} is the multiplicity of the irreducible representation corresponding to \lambda in the induced representation of S_n from the trivial representation of S_0, which is the regular representation.)

More generally, given a word w = w_n w_{n-1} ... w_1 on \{ U, D \}, a Hasse walk of type w is a walk on Young’s lattice starting at the empty partition in which one takes a step of type w_1 (add or remove a box), then a step of type w_2 (add or remove a box), and so forth. Clearly not all words give rise to valid walks; those words that do will be called valid, and it’s not hard to characterize them. We let \alpha(w, \lambda) denote the number of such walks which end at \lambda, hence w_n w_{n-1} ... w_1 \emptyset = \sum_{\lambda} \alpha(w, \lambda) \lambda where \lambda ranges over all partitions of the right size.

Theorem: Given a valid word w = w_n w_{n-1} ... w_1, let S_w = \{ i | w_i = D \}. For each i \in S_w, let a_i be the number of Ds to the right of w_i and let b_i be the number of Us to the right of w_i. Then

\displaystyle \alpha(w, \lambda) = f^{\lambda} \prod_{i=1}^{n} (b_i - a_i).

Corollary: \displaystyle \alpha(D^n U^n, \emptyset) = \sum_{\lambda \vdash n} (f^{\lambda})^2 = n!.

The proof can be found in Stanley’s notes, so I won’t repeat it except to say that it depends only on the differential property. Moreover, it does not depend at any point on the fact that the symmetric groups have size n!. In the notes and in his paper, Stanley describes a number of other combinatorial results one can arrive at in this way, but they would take us too far afield.

This entry was posted on November 2, 2009 at 9:21 am and is filed under algebraic combinatorics, representation theory.

Tags: , ,

One Response to “Young’s lattice”

  1. Ben Webster Says:

    November 5, 2009 at 7:01 am

    Yeah, that answer was not my best moment. I’m gone back through and explained what I was saying a bit more carefully.

    Reply

Leave a Reply