Feeds:
Posts
Comments

Posts Tagged ‘Young tableaux’

The Jacobi-Trudi identities

Posted in math.CO, math.RT, tagged , , on November 20, 2009| 4 Comments »

Today I’d like to introduce a totally explicit combinatorial definition of the Schur functions. Let \lambda \vdash n be a partition. A semistandard Young tableau T of shape \lambda is a filling of the Young diagram of \lambda with positive integers that are weakly increasing along rows and strictly increasing along columns. The weight of a tableau T is defined as \mathbf{x}^T = x_1^{T_1} x_2^{T_2} ... where T_i is the total number of times i appears in the tableau.

Definition 4: \displaystyle s_{\lambda}(x_1, x_2, ...) = \sum_T \mathbf{x}^T

where the sum is taken over all semistandard Young tableaux of shape \lambda.

As before we can readily verify that s_{(k)} = h_k, s_{(1^k)} = e_k. This definition will allow us to deduce the Jacobi-Trudi identities for the Schur functions, which describe among other things the action of the fundamental involution \omega. Since I’m trying to emphasize how many different ways there are to define the Schur functions, I’ll call these definitions instead of propositions.

Definition 5: \displaystyle s_{\lambda}= \det(h_{\lambda_i+j-i})_{1 \le i, j \le n}.

Definition 6: \displaystyle s_{\lambda'} = \det(e_{\lambda_i+j-i})_{1 \le i, j \le n}.

(more…)

Read Full Post »

Young’s lattice

Posted in math.CO, math.RT, tagged , on November 2, 2009| 3 Comments »

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.

(more…)

Read Full Post »

Standard Young tableaux and Robinson-Schensted-Knuth

Posted in math.CO, math.RT, tagged on July 22, 2009| 8 Comments »

Earlier I mentioned that the theory of Young tableaux is the source of one of my favorite proofs. Today I’d like to present, again from the theory of Young tableaux, one of my favorite pairs of proofs.

A standard Young tableau is a chain in Young’s lattice; equivalently, it is a sequence of Young diagrams, each of which has exactly one more box than the previous. One can succinctly write down such a chain by taking the last Young diagram in the chain and recording the “path” traced out by the rest of the chain: write down a 1 in the box corresponding to the first Young diagram, a 2 in the box added by the next Young diagram, and so forth. In other words, a standard Young tableau is a Young tableau filled with positive integers 1, 2, ... n which is strictly increasing across rows and columns.

Given a Young diagram \lambda, let f^{\lambda} denote the number of standard Young tableaux of shape \lambda; equivalently, one can define L(\lambda) to be the poset of Young diagrams fitting inside \lambda, and then f^{\lambda} is equal to the number of maximal chains of L(\lambda).

Finally, one last bit of notation. If \lambda is a Young diagram for a partition of n, we will write either |\lambda| = n or \lambda \vdash n. Then we have the following beautiful result.

Theorem: \displaystyle \sum_{\lambda \vdash n} (f^{\lambda})^2 = n!.

(more…)

Read Full Post »

GILA V: The Polya enumeration theorem and applications

Posted in math.CO, math.NT, tagged , , , on June 21, 2009| 7 Comments »

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors 1, 2, ... n (represented by variables r_1, r_2, ... r_n), and we have a set of slots S with |S| = m acted on by a group G where each slot will be assigned a color. Define f_G(t_1, ... t_n) to be the number of orbits of functions S \to \{ 1, 2, ... n \} under the action of G where color i is used t_i times. (Since the action of G only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

\displaystyle F_G(r_1, r_2, ... r_n) = \sum_{t_1 + ... + t_n = m} f_G(t_1, t_2, ... t_n) r_1^{t_1} r_2^{t_2} ... r_n^{t_n}.

Note that setting r_1 = r_2 = .... = r_n = 1 we recover F_G(n), which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |(r_1, r_2, ... r_n)

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?

(more…)

Read Full Post »

Young diagrams, q-analogues, and one of my favorite proofs

Posted in math.CO, tagged , , on June 11, 2009| 10 Comments »

I’ve decided to start blogging a little more about the algebraic combinatorics I’ve learned over the past year. In particular, I’d like to present one of my favorite proofs from Stanley’s Enumerative Combinatorics I.

The theory of Young tableaux is a great example of the richness of modern mathematics: although they can be defined in an elementary combinatorial fashion, interest in the theory is primarily driven (as I understand it) by their applications to representation theory and other fields of mathematics. The standard application is in describing the irreducible representations of the symmetric group in characteristic zero. I’ll be describing a more elementary aspect of the theory: the relationship between Young diagrams and q-binomial coefficients.

Young diagrams can be defined as a visual representations of partitions. A partition of k is a weakly decreasing sequence \lambda_1 \ge \lambda_2 \ge ... \ge \lambda_i such that \lambda_1 + ... + \lambda_i = k. Partitions uniquely describe cycle decompositions, hence conjugacy classes, of the symmetric group, which is a hint at the connection to representation theory. A Young diagram of the partition \lambda consists of i rows of boxes where the j^{th} row has \lambda_j boxes. Let L(m, n) denote the poset of Young diagrams that fit into an m \times n box, ordered by inclusion: equivalently, one can define the full Young lattice and define L(m, n) to be the elements less than or equal to the m \times n partition. (One can then define a standard Young tableau to be a chain in the Young lattice, but we will not need this notion.) One can easily check that the following is true.

Proposition: |L(m, n)| = {m+n \choose m}.

The rest of this post explains the q-analogue of this result.

(more…)

Read Full Post »