💁🏽Algebraic Combinatorics Unit 5 – Partitions and Young Tableaux

Key Concepts and Definitions

• Partitions represent the decomposition of a positive integer into a sum of smaller positive integers (parts)
• Young diagrams visually depict integer partitions as left-justified arrays of boxes
• Ferrers diagrams are similar to Young diagrams but use dots instead of boxes
• Young tableaux are Young diagrams filled with positive integers that follow specific rules
  • Standard Young tableaux have entries that increase along rows and columns
  • Semi-standard Young tableaux allow repeated entries in rows but must still increase along columns
• Conjugate partitions swap the rows and columns of a Young diagram
• Hook length formula calculates the number of standard Young tableaux for a given shape

Historical Context and Applications

• Partition theory originated in the 18th century with Leonhard Euler's work on integer partitions
• Young tableaux were introduced by Alfred Young in 1900 to study the symmetric group
• Partitions and Young tableaux have applications in various fields:
  • Combinatorics for counting and enumerating objects
  • Representation theory for studying algebraic structures (groups, algebras)
  • Statistical mechanics for modeling particle configurations
• Young tableaux are used in the Robinson-Schensted-Knuth (RSK) correspondence, connecting permutations and pairs of standard Young tableaux
• Schur functions, which are symmetric polynomials, are related to semi-standard Young tableaux

Partition Theory Fundamentals

• Partitions of a positive integer $n$ are written as $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)$, where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_k > 0$ and $\sum_{i=1}^k \lambda_i = n$
• The partition function $p(n)$ counts the number of partitions of $n$
  • Generating function for $p(n)$: $\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac{1}{1-x^k}$
• Conjugate partitions $\lambda'$ satisfy $\lambda'_i = |\{j : \lambda_j \geq i\}|$
• Dominance order compares partitions: $\lambda \trianglerighteq \mu$ if $\sum_{i=1}^k \lambda_i \geq \sum_{i=1}^k \mu_i$ for all $k$
• Partitions with distinct parts (no repeated parts) have generating function $\prod_{k=1}^\infty (1+x^k)$

Young Diagrams and Ferrers Diagrams

• Young diagrams represent partitions as arrays of left-justified boxes
  • The $i$-th row has $\lambda_i$ boxes
• Ferrers diagrams use dots instead of boxes
• The size of a Young diagram is the total number of boxes, equal to the integer being partitioned
• The conjugate of a Young diagram is obtained by reflecting the diagram about its main diagonal
• Skew Young diagrams are obtained by removing a smaller Young diagram from the top-left corner of a larger one

Young Tableaux: Construction and Properties

• Standard Young tableaux (SYT) are filled with the numbers 1 to n, increasing along rows and columns
• Semi-standard Young tableaux (SSYT) allow repeated entries in rows, still increasing along columns
• The number of SYT of shape $\lambda$ is given by the hook length formula: $f^\lambda = \frac{n!}{\prod_{u \in \lambda} h(u)}$, where $h(u)$ is the hook length of cell $u$
• The Robinson-Schensted-Knuth (RSK) correspondence bijectively maps permutations to pairs of SYT of the same shape
• Knuth equivalence relates permutations that map to the same insertion tableau under RSK
• Evacuation is an involution on SYT that reverses the order of the entries while preserving shape

Algebraic Representations and Symmetries

• Young tableaux are closely related to the representation theory of the symmetric group $S_n$
• Irreducible representations of $S_n$ are indexed by partitions of $n$
• The Specht module $S^\lambda$ is a subspace of the group algebra of $S_n$, constructed using Young symmetrizers
• Schur-Weyl duality connects the representation theory of $S_n$ and $GL(V)$
• Schur functions $s_\lambda$ are symmetric polynomials associated with SSYT of shape $\lambda$
  • They form a basis for the ring of symmetric functions
• Kostka numbers $K_{\lambda\mu}$ count the number of SSYT of shape $\lambda$ and content $\mu$

Algorithms and Computational Aspects

• The Robinson-Schensted (RS) algorithm bijectively maps permutations to pairs of SYT
  • Insertion algorithm: builds the insertion tableau by inserting elements of the permutation
  • Recording algorithm: keeps track of the order of insertions to create the recording tableau
• The Schensted algorithm calculates the length of the longest increasing subsequence in a permutation
• Jeu de taquin (sliding game) is a procedure for moving boxes in a skew Young tableau to obtain a standard Young tableau
• Littlewood-Richardson rule determines the coefficients in the product of Schur functions
• Efficient algorithms exist for generating and enumerating Young tableaux and partitions

Advanced Topics and Current Research

• Combinatorial Hopf algebras, such as the Malvenuto-Reutenauer algebra and the Loday-Ronco algebra, are related to Young tableaux and permutations
• Kazhdan-Lusztig theory studies cells in the Hecke algebra of a Coxeter group, generalizing the RSK correspondence
• Macdonald polynomials are a family of symmetric functions that generalize Schur functions and Hall-Littlewood polynomials
• Crystal bases, from quantum group theory, have a combinatorial realization using Young tableaux
• Enumeration of Young tableaux with specific properties (e.g., bounded height, bounded entries) is an active area of research
• Connections between Young tableaux and other combinatorial objects (e.g., alternating sign matrices, plane partitions) continue to be explored