Feeds:
Posts
Comments

## 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 $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 $D$s to the right of $w_i$ and let $b_i$ be the number of $U$s 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.

### 3 Responses

1. […] of , and the number of arrows from to is the multiplicity of in . (Compare the construction of Young’s lattice from representations of the symmetric groups.) Then the multiplicity of the trivial representation […]

2. Thank you,
very interesting article

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