Young lattice

Definition

In terms of partitions

The Young lattice or Young graph is an infinite ranked graph (with one rank or level for each natural number $n$ ) constructed as follows. For each natural number $n$ , the vertices at level $n$ are precisely the partitions of $n$ . We draw an edge connecting a partition of $n$ and a partition of $n + 1$ if the Young diagram (also called Ferrers diagram) for the partition of $n + 1$ can be obtained by inserting one block into the Young diagram of the partition of $n$ . In algebraic terms, this means that the partition of $n + 1$ is obtained from the partition of $n$ either by incrementing one of the parts by $1$ or by adding a new part with value $1$ .

The levels are typically drawn as vertical columns with level increasing from left to right.

In some conventions, this graph is viewed as a directed graph (with the edge from $n$ to $n + 1$ ) whereas in other conventions, the graph is considered undirected. The undirected convention is often used to keep in mind that it is useful to move in both the forward and reverse directions.

Here's how the Young graph looks where the partitions are written arithmetically:

Note that the Young graph is not planar.

Here's how the Young graph looks where each partition is represented by its Young diagram: (to be inserted).

As a Bratteli diagram

The Young graph is the Bratteli diagram for the inductive sequence of symmetric groups $S_{1} ↪ S_{2} ↪ S_{3} ↪ \dots ↪ S_{n} ↪$ , or more precisely, for the inductive sequence of the corresponding group rings over $C$ .

Facts

The Young graph, viewed as a Bratteli diagram, stores a lot of combinatorial data about the representations of the symmetric groups on finite sets. For more on this, see linear representation theory of symmetric groups. Here's a quick summary:

The vertices at level $n$ correspond to the irreducible representations of the symmetric group of degree $n$ .
The targets of edges going from a vertex at level $n$ to level $n + 1$ correspond to the irreducible components of the representation of $S_{n + 1}$ [[induced from the starting representation of $S_{n}$ .
The sources of edges going to a vertex at level $n + 1$ from a vertex at level $n$ correspond to the irreducible components of the representation of the representation of $S_{n}$ obtained by restriction of representation from the representation of $S_{n + 1}$ .

Properties

Conjugation symmetry

The operation of taking a partition to its conjugate partition is a symmetry of the Young graph. In the portion shown in the diagram, this symmetry can be achieved by reflecting about the horizontal line through the vertex for the partition of $1$ . Conjugation symmetry on the Young graph corresponds, in the world of linear representations, to tensoring with the sign representation. In particular, it preserves the degree of an irreducible representation.