5.3 Standard and Semistandard Young Tableaux

Young tableaux are powerful tools in algebraic combinatorics, representing partitions as diagrams filled with numbers. They come in two main types: standard tableaux, using each number once, and semistandard tableaux, allowing repeats. These structures are crucial for understanding symmetries and patterns.

Young tableaux have wide-ranging applications in math and physics. They're key to studying symmetric group representations, symmetric functions, and crystal bases. Their properties and operations, like the Schützenberger involution, reveal deep connections between seemingly unrelated mathematical concepts.

Standard vs Semistandard Young Tableaux

Definitions and Properties

Top images from around the web for Definitions and Properties

• 

  Category:Young tableaux - Wikimedia Commons View original

  Is this image relevant?

• 

  Young tableau - Wikipedia View original

  Is this image relevant?

• 

  Category:Young tableaux - Wikimedia Commons View original

  Is this image relevant?

• 

  Young tableau - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Definitions and Properties

• 

  Category:Young tableaux - Wikimedia Commons View original

  Is this image relevant?

• 

  Young tableau - Wikipedia View original

  Is this image relevant?

• 

  Category:Young tableaux - Wikimedia Commons View original

  Is this image relevant?

• 

  Young tableau - Wikipedia View original

  Is this image relevant?

1 of 2

• A Young tableau fills the boxes of a Young diagram with positive integers that are weakly increasing across rows and strictly increasing down columns
• A standard Young tableau has the additional property that the filling must use each number from 1 to n exactly once, where n is the number of boxes
• A semistandard Young tableau allows repeated entries, but they must still increase weakly across rows and strictly down columns
• The shape of a Young tableau is the underlying Young diagram, represented by a partition λ = (λ₁, λ₂, ..., λₖ)
  • For example, the partition (4, 2, 1) represents a Young diagram with 4 boxes in the first row, 2 in the second, and 1 in the third
• The content of a tableau is the composition α = (α₁, α₂, ...) where αᵢ counts the number of occurrences of i in the tableau
  • For instance, a tableau with content (2, 1, 3) has two 1s, one 2, and three 3s

Schützenberger Involution

• The Schützenberger involution is an operation on semistandard tableaux that preserves the shape but changes the content
• It is defined by a sequence of jeu de taquin slides that move the largest entry to the southeast corner, the second largest to the next southeast corner, and so on
• The Schützenberger involution is an involution, meaning that applying it twice returns the original tableau
• It has important applications in the theory of crystal bases and the RSK correspondence

Constructing Young Tableaux

Constructing Standard Young Tableaux

• To construct a standard Young tableau, fill the boxes with the numbers 1 to n so that entries increase along rows and down columns
• The number of standard Young tableaux of shape λ is given by the Hook Length Formula
  • The Hook Length Formula states that the number of standard tableaux is n! divided by the product of all hook lengths in the diagram
  • For example, the hook lengths of the partition (3, 2) are 4, 2, 1, 3, 1, so the number of standard tableaux is 5!/(4 * 2 * 1 * 3 * 1) = 5

Constructing Semistandard Young Tableaux

• To construct a semistandard Young tableau, fill the boxes with positive integers so that entries weakly increase along rows and strictly increase down columns
• The Schensted Insertion Algorithm can be used to insert a positive integer into a semistandard tableau, bumping entries to maintain the semistandard property
  • For instance, inserting 3 into the first row of [[1, 2, 2], [2, 3]] bumps the 2 to the second row, bumps the 3 to a new row, and inserts 3 into the vacated box, yielding [[1, 2, 3], [2], [3]]
• The Robinson-Schensted-Knuth (RSK) correspondence bijectively maps matrices with non-negative integer entries to pairs of semistandard tableaux of the same shape
  • The row-insertion tableau is constructed by inserting the entries of each row of the matrix, while the column-recording tableau tracks which row each new box originated from
  • For example, the matrix [[1, 0, 2], [0, 1, 1]] maps to the pair ([[1, 2, 2], [3]], [[1, 1, 2], [2]])

Enumerating Young Tableaux

Standard Young Tableaux

• The number of standard Young tableaux of shape λ is given by the Hook Length Formula: n! divided by the product of all hook lengths in the diagram
• The hook length of a box is the number of boxes directly below or directly to the right of it in the diagram, including the box itself
  • In the diagram of (3, 2), the hook lengths are 4, 2, 1 in the first row and 3, 1 in the second row
• There are simple formulas for the number of standard tableaux of certain shapes, such as rectangles (the binomial coefficient) and staircases (the Catalan numbers)

Semistandard Young Tableaux

• The number of semistandard Young tableaux of shape λ with content α is given by the Kostka number K_{λ,α}
• Kostka numbers can be computed using the Kostant Multiplicity Formula, which involves a sum over the Weyl group
  • For the partition (2, 1) and content (2, 1), the Weyl group S_3 has elements {1, s_1, s_2, s_1s_2, s_2s_1, s_1s_2s_1}, and the Kostant partition function yields K_{(2,1),(2,1)} = 2
• The generating function for Kostka numbers is given by the Schur polynomial s_λ(x₁, x₂, ...)
  • The coefficient of x₁^α₁ x₂^α₂ ... in s_λ is the Kostka number K_{λ,α}
  • For example, s_{(2,1)}(x₁, x₂) = x₁^2 x₂ + x₁ x₂^2, so K_{(2,1),(2,1)} = 1 and K_{(2,1),(1,2)} = 1

Applications of Young Tableaux

Representation Theory

• The irreducible representations of the symmetric group S_n are indexed by partitions of n, with the dimension given by the number of standard Young tableaux of that shape
  • For instance, the partition (3, 1) of 4 corresponds to the irreducible representation of S_4 of dimension 3
• The Specht module S^λ is a construction of the irreducible representation corresponding to λ, with a basis indexed by standard tableaux of shape λ
  • The action of a permutation on a tableau is given by applying it to the entries, then straightening the resulting filling using jeu de taquin slides
  • For example, in S^(3,1), the permutation (1 2) sends the standard tableau [[1, 2, 3], [4]] to [[1, 2, 4], [3]]

Symmetric Functions

• The Schur polynomials s_λ form a basis for the ring of symmetric functions and can be defined as the generating functions for semistandard tableaux of shape λ
  • The coefficient of x₁^α₁ x₂^α₂ ... in s_λ is the number of semistandard tableaux of shape λ and content α
  • For example, s_{(2,1)}(x₁, x₂) = x₁^2 x₂ + x₁ x₂^2 + x₁^3 + x₂^3, corresponding to the tableaux [[1,1],[2]], [[1,2],[2]], [[1,1],[1]], and [[2,2],[2]]
• The Littlewood-Richardson Rule expresses the product of two Schur polynomials as a sum of Schur polynomials, with coefficients given by Littlewood-Richardson tableaux
  • A Littlewood-Richardson tableau is a semistandard tableau whose reverse reading word is a lattice permutation
  • For example, s_{(2,1)} s_{(1)} = s_{(3,1)} + s_{(2,2)} + s_{(2,1,1)}, as seen from the tableaux [[1,1,2],[3]], [[1,1],[2,3]], and [[1,3],[2],[3]]
• The RSK correspondence gives a bijective proof of the Cauchy Identity, which expresses a sum of products of Schur polynomials as a product of sums
  • Applying RSK to a matrix M yields a pair of tableaux (P(M), Q(M)), and the sum over all M of x^M y^{P(M)} z^{Q(M)} is the Cauchy identity
• The Pieri Rule and Branching Rule for Schur polynomials can be proven using semistandard tableaux and Schensted insertion
  • The Pieri Rule states that s_λ s_{(k)} is the sum of all s_μ where μ/λ is a horizontal strip of size k
  • The Branching Rule states that s_λ(x₁, ..., x_n) is the sum of all s_μ(x₁, ..., x_{n-1}) where λ/μ is a valid skew shape