nLab
Young diagram

Contents

The idea

Young diagrams are used to describe many objects in algebra and combinatorics, including:

  • integer partitions. For example, the integer partition
17=5+4+4+2+1+1 17 = 5 + 4 + 4 + 2 + 1 + 1

is drawn as the Young diagram

<!-- Created with SVG-edit - http://svg-edit.googlecode.com/ --> Young diagram (5,4,4,2,1,1) Layer 1
  • conjugacy classes in S nS_n.

  • irreducible representations of the symmetric groups S nS_n over any field of characteristic zero

  • irreducible algebraic representations of the special linear groups SL(N,)SL(N,\mathbb{C})

  • irreducible unitary representations of the special unitary groups SU(N)SU(N)

  • elementary symmetric functions

  • Schur functors

  • basis vectors for the free lambda-ring on one generator, Λ\Lambda

  • flag varieties for the special linear groups SL(N,k)SL(N,k), where kk is any field

  • characteristic classes for complex vector bundles: that is, cohomology classes on the classifying spaces of the general linear groups GL(N,)GL(N,\mathbb{C})

  • characteristic classes for hemitian vector bundles: that is, cohomology classes on the [classifying spaces]] of the unitary groups U(N)U(N)

  • finite-dimensional C *{}^*-algebras: any such algebra is of the form M n 1()M n k()M_{n_1}(\mathbb{C}) \oplus \cdots \oplus M_{n_k}(\mathbb{C}) for some unique list of natural numbers n 1n 2n kn_1 \ge n_2 \ge \cdots \ge n_k.

  • finite abelian pp-groups: any such group is of the form /p n 1/p n k\mathbb{Z}/p^{n_1} \oplus \cdots \oplus \mathbb{Z}/p^{n_k} for some unique list of natural numbers n 1n 2n kn_1 \ge n_2 \ge \cdots \ge n_k.

  • finite commutative semisimple algebras over 𝔽 p\mathbb{F}_p: any such algebra is of the form 𝔽 p n 1𝔽 p n k\mathbb{F}_{p^{n_1}} \oplus \cdots \oplus \mathbb{F}_{p^{n_k}} for some unique list of natural numbers n 1n 2n kn_1 \ge n_2 \ge \cdots \ge n_k.

  • the trace of the category of finite sets has isomorphism classes of objects corresponding to Young diagrams.

Young diagram

A Young diagram F λF^\lambda, also called Ferrers diagram, is a graphical representation of an unordered integer partition λ=(λ 1λ 2λ l\lambda = (\lambda_1\ge\lambda_2\ge\ldots\ge\lambda_l). If λn\lambda\vdash n is a partition of nn then the Young diagram has nn boxes. A partition can be addressed as a multiset over \mathbb{N}.

There are two widely used such representations. The English one uses matrix-like indices, and the French one uses Cartesian coordinate-like indices for the boxes x i,jx_{i,j} in the diagram F λF^\lambda.

In the English representation the boxes are adjusted to the north-west in the 4th quadrant of a 2-dimensional Cartesian coordinate system, with the ‘y’-axis being downward oriented. For instance the diagram F (5,4,4,2,1,1)F^{(5,4,4,2,1,1)} representing the partition (5,4,4,2,1,1)(5,4,4,2,1,1) of 1717 is given in the English representation as:

<!-- Created with SVG-edit - http://svg-edit.googlecode.com/ --> Young diagram (5,4,4,2,1,1) Layer 1

Let 𝕐\mathbb{Y} be the set of Young diagrams. Important functions on Young diagrams include:

  • conjugation: denoted by a prime :𝕐𝕐\prime : \mathbb{Y} \rightarrow \mathbb{Y} reflects the Young diagram along its main diagonal (north-west to south-east). In the above example the conjugated partition would be λ =(6,4,3,3,1)\lambda^\prime=(6,4,3,3,1).
  • weight: wt:𝕐wt \colon \mathbb{Y} \rightarrow \mathbb{N} provides the number of boxes.
  • length: :𝕐\ell \colon \mathbb{Y} \rightarrow \mathbb{N} provides the number of rows or equivalently the number of positive parts of the partition λ\lambda. The length of the conjugated diagram gives the number of columns.
  • plus: +:𝕐×𝕐𝕐::(μ,ν)μ+ν=(μ 1+ν 1,,μ l+ν l)+ \colon \mathbb{Y}\times \mathbb{Y} \rightarrow \mathbb{Y} :: (\mu,\nu) \mapsto \mu + \nu = (\mu_1+\nu_1,\ldots,\mu_l+\nu_l)
  • times: ×:𝕐×𝕐𝕐::(μ,ν)(μν) \times \colon \mathbb{Y}\times \mathbb{Y} \rightarrow \mathbb{Y} :: (\mu,\nu) \mapsto (\mu \cup \nu)_{\ge} the unordered union of the multisets. It follows that μ×ν=(μ +ν ) \mu\times \nu =(\mu^\prime + \nu^\prime)^\prime.

A filling of a Young diagram with elements from a set SS is called a Young tableau?.

Skew Young diagram

A generalization of a Young diagram is a skew Young diagram. Let μ,ν\mu,\nu be two partitions, and let νμ\nu \le \mu be defined as i:ν iμ i\forall i : \nu_i\le \mu_i (possibly adding trailing zeros). The skew Young diagram F μ/νF^{\mu/\nu} is given by the Young diagram F μF^\mu with all boxes belonging to F νF^\nu when superimposed removed. If μ=(5,4,4,2,1,1)\mu=(5,4,4,2,1,1) and ν=(3,3,2,1)\nu=(3,3,2,1) then F μ/νF^{\mu/\nu} looks like:

<!-- Created with SVG-edit - http://svg-edit.googlecode.com/ --> Skew Young diagram (5,4,4,2,1,1)/(3,3,2,1) Layer 1
  • A skew diagram is called connected if all boxes share an edge.
  • A skew diagram is called a horizontal strip if every column contains at most one box.
  • A skew diagram is called a vertical strip if every row contains at most one box.
  • conjugation, weight, length extend to skew diagrams accordingly.

References

For a quick online introduction to Young diagrams, try:

  • Alexander Yong, What is … a Young Tableau, Notices of the American Mathematical Society 54 (February 2007), 240–241. (pdf)

A nice introduction to Young diagrams can be found here:

  • William Fulton and Joe Harris, Representation Theory: a First Course, Springer, Berlin, 1991.

A more detailed reference is:

  • William Fulton, Young Tableaux, with Applications to Representation Theory and Geometry, Cambridge U. Press, 1997.

A connection to algebraic geometry:

  • C. de Concini,D. Eisenbud, C. Procesi, Young diagrams and determinantal varieties, Invent. Math. 56 (1980), 129-165.

category: combinatorics

Revised on September 18, 2012 12:51:31 by Tim Porter (95.147.237.54)