Young's lattice

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 of symmetric groups (where and 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 are the Young diagrams with boxes.

It turns out that this “poset” is a genuine poset; in other words, in the restriction of an irreducible representation of to an irreducible representation of , the resulting representation contains each irreducible representation at most once. In fact, much more is true. In a poset we write if and there is no with ; this relation is called covering. So elements of rank cover elements of rank .

Theorem (Branching Rule): if and only if is obtained from 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 denote the rank of order , where contains only the empty partition . Let denote the free vector space on , which is graded by rank, hence

.

We can think of elements of as generalizing direct sums of irreducible representations of . From this perspective, comes equipped with two distinguished linear operators such that

and

.

restrict to operators and 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 .

The differential property

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

Proposition: .

Proof. Suppose a Young diagram has 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 cancel. If we add and remove the same box, there are ways to do this. However, if we remove and add the same box, there are ways to do this. Hence 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 on 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 -differential because behaves like ; see Stanley’s paper for more discussion.

The upshot of all of this is that polynomials in can be written as a unique linear combination of terms of the form 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,

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

More generally, given a word on , a Hasse walk of type is a walk on Young’s lattice starting at the empty partition in which one takes a step of type (add or remove a box), then a step of type (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 denote the number of such walks which end at , hence where ranges over all partitions of the right size.

Theorem: Given a valid word , let . For each , let be the number of s to the right of and let be the number of s to the right of . Then

.

Corollary: .

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 . 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.

About these ads