💁🏽Algebraic Combinatorics Unit 10 – Tableaux and Schur Functions in Combinatorics

Key Concepts and Definitions

• Partition: a non-increasing sequence of positive integers $\lambda = (\lambda_1, \lambda_2, \ldots, \lambda_k)$ where $\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_k > 0$
• Young diagram: a graphical representation of a partition, consisting of left-justified rows of boxes with $\lambda_i$ boxes in the $i$-th row
  • Conjugate partition $\lambda'$: obtained by transposing the Young diagram of $\lambda$, i.e., swapping rows and columns
• Young tableau: a Young diagram filled with positive integers that are strictly increasing along rows and weakly increasing down columns
  • Standard Young tableau (SYT): a Young tableau with entries $1, 2, \ldots, n$, each appearing exactly once
• Schur function $s_\lambda(x_1, \ldots, x_n)$: a symmetric polynomial associated with a partition $\lambda$, defined as a sum over all semistandard Young tableaux of shape $\lambda$
  • Schur functions form a basis for the ring of symmetric polynomials
• Kostka number $K_{\lambda,\mu}$: the number of semistandard Young tableaux of shape $\lambda$ and content $\mu$
• Littlewood-Richardson coefficient $c_{\lambda,\mu}^\nu$: the number of Littlewood-Richardson tableaux of shape $\nu/\lambda$ and content $\mu$, which appears in the product of Schur functions $s_\lambda \cdot s_\mu = \sum_\nu c_{\lambda,\mu}^\nu s_\nu$

Historical Context and Development

• Tableaux and Schur functions have roots in the work of Alfred Young (1873-1940) and Issai Schur (1875-1941) in the early 20th century
• Young introduced the concept of Young tableaux in his study of the symmetric group and the representation theory of $S_n$
• Schur developed Schur functions as characters of polynomial representations of the general linear group $GL(n)$
• The Littlewood-Richardson rule, discovered by Dudley Littlewood and Archibald Richardson in the 1930s, provides a combinatorial interpretation of the product of Schur functions
• The Robinson-Schensted-Knuth (RSK) correspondence, developed by Gilbert de Beauregard Robinson, Craige Schensted, and Donald Knuth, establishes a bijection between permutations and pairs of standard Young tableaux
• The Schützenberger involution, introduced by Marcel-Paul Schützenberger in the 1960s, is a fundamental operation on Young tableaux that relates to the RSK correspondence and the Littlewood-Richardson rule
• The study of tableaux and Schur functions has grown to encompass connections with various areas of mathematics, including representation theory, algebraic geometry, and enumerative combinatorics

Young Tableaux Fundamentals

• A Young tableau is a filling of a Young diagram with positive integers that follow specific rules
  • Entries strictly increase from left to right along rows
  • Entries weakly increase from top to bottom down columns
• The shape of a Young tableau is the underlying partition $\lambda$, while the content is the composition $\mu = (\mu_1, \mu_2, \ldots)$ where $\mu_i$ is the number of occurrences of $i$ in the tableau
• A standard Young tableau (SYT) is a Young tableau with entries $1, 2, \ldots, n$, each appearing exactly once
  • The number of SYT of shape $\lambda$ is given by the famous Hook Length Formula: $f^\lambda = \frac{n!}{\prod_{u \in \lambda} h(u)}$, where $h(u)$ is the hook length of the cell $u$
• Semistandard Young tableaux (SSYT) allow for repeated entries but maintain the increasing conditions along rows and columns
  • The number of SSYT of shape $\lambda$ and content $\mu$ is the Kostka number $K_{\lambda,\mu}$
• The Robinson-Schensted-Knuth (RSK) correspondence establishes a bijection between permutations of $S_n$ and pairs of SYT of the same shape with $n$ boxes
• Jeu de taquin is a sliding operation on Young tableaux that preserves the tableau properties and plays a crucial role in the Littlewood-Richardson rule and the Schützenberger involution

Schur Functions: Introduction and Properties

• Schur functions $s_\lambda(x_1, \ldots, x_n)$ are a family of symmetric polynomials indexed by partitions $\lambda$
  • They form a basis for the ring of symmetric polynomials $\Lambda_n = \mathbb{Z}[x_1, \ldots, x_n]^{S_n}$
• Schur functions can be defined in several equivalent ways:
  • As a sum over all semistandard Young tableaux of shape $\lambda$: $s_\lambda = \sum_{T} x^T$, where $x^T = x_1^{\mu_1} x_2^{\mu_2} \cdots$ and $\mu$ is the content of $T$
  • As a ratio of alternants: $s_\lambda = \frac{a_{\lambda+\delta}}{a_\delta}$, where $a_\alpha = \det(x_i^{\alpha_j})_{1 \leq i,j \leq n}$ and $\delta = (n-1, n-2, \ldots, 1, 0)$
  • As a specialization of the Hall-Littlewood polynomial: $s_\lambda = P_\lambda(x; 0)$
• Schur functions satisfy several important properties:
  • Stability: $s_\lambda(x_1, \ldots, x_n, 0) = s_\lambda(x_1, \ldots, x_n)$
  • Orthogonality: $\langle s_\lambda, s_\mu \rangle = \delta_{\lambda,\mu}$ with respect to the Hall inner product
  • Cauchy identity: $\sum_{\lambda} s_\lambda(x) s_\lambda(y) = \prod_{i,j} (1 - x_i y_j)^{-1}$
• The product of Schur functions can be expanded using the Littlewood-Richardson coefficients: $s_\lambda \cdot s_\mu = \sum_\nu c_{\lambda,\mu}^\nu s_\nu$
  • The coefficients $c_{\lambda,\mu}^\nu$ count the number of Littlewood-Richardson tableaux of shape $\nu/\lambda$ and content $\mu$

Connections to Representation Theory

• Schur functions are deeply connected to the representation theory of the symmetric group $S_n$ and the general linear group $GL(n)$
• The irreducible representations of $S_n$ are indexed by partitions $\lambda$ of $n$, and their characters are given by the Schur functions $s_\lambda$
  • The dimension of the irreducible representation corresponding to $\lambda$ is the number of standard Young tableaux of shape $\lambda$
• The polynomial representations of $GL(n)$ are also indexed by partitions $\lambda$, and their characters are the Schur functions $s_\lambda(x_1, \ldots, x_n)$
  • The dimension of the polynomial representation corresponding to $\lambda$ is the number of semistandard Young tableaux of shape $\lambda$ with entries from $\{1, \ldots, n\}$
• The Littlewood-Richardson coefficients $c_{\lambda,\mu}^\nu$ appear in the decomposition of tensor products of irreducible representations of $GL(n)$: $V_\lambda \otimes V_\mu = \bigoplus_\nu c_{\lambda,\mu}^\nu V_\nu$
• The Kostka numbers $K_{\lambda,\mu}$ are the multiplicities of the weight $\mu$ in the polynomial representation corresponding to $\lambda$
• The RSK correspondence provides a combinatorial realization of the decomposition of the regular representation of $S_n$ into irreducible representations
• The Schur-Weyl duality relates the representations of $S_n$ and $GL(n)$ through their actions on tensor powers of the fundamental representation of $GL(n)$

Algorithms and Computational Techniques

• Computing Kostka numbers and Littlewood-Richardson coefficients is a central problem in the combinatorics of tableaux and Schur functions
• The Littlewood-Richardson rule provides a combinatorial method to compute $c_{\lambda,\mu}^\nu$ by enumerating Littlewood-Richardson tableaux
  • Efficient algorithms exist for generating Littlewood-Richardson tableaux, such as the Remmel-Whitney algorithm and the rectification-based approach using jeu de taquin
• The RSK correspondence can be used to compute Kostka numbers by enumerating semistandard Young tableaux
  • The Schensted insertion algorithm and its variations (e.g., Edelman-Greene insertion) provide efficient methods to construct the RSK correspondence
• The hook-content formula expresses Kostka numbers as a sum over the cells of the Young diagram: $K_{\lambda,\mu} = \prod_{u \in \lambda} \frac{c(u)}{h(u)}$, where $c(u)$ is the content of the cell $u$
• Combinatorial interpretations of Schur functions lead to efficient algorithms for their computation
  • The Jacobi-Trudi formula expresses Schur functions as determinants of complete homogeneous symmetric polynomials
  • The dual Jacobi-Trudi formula expresses Schur functions as determinants of elementary symmetric polynomials
• The Murnaghan-Nakayama rule provides a combinatorial formula for the characters of the symmetric group in terms of ribbon tableaux
• The Lascoux-Schützenberger charge statistic on tableaux gives a combinatorial interpretation of the Hall-Littlewood polynomials and their connection to Kostka-Foulkes polynomials

Applications in Related Fields

• Tableaux and Schur functions have found numerous applications in various areas of mathematics and beyond
• In algebraic geometry, Schur functions appear as representatives of Schubert classes in the cohomology of Grassmannians and flag varieties
  • The Littlewood-Richardson coefficients describe the structure constants of the cohomology ring with respect to the Schubert basis
• In enumerative combinatorics, tableaux and Schur functions are used to count various combinatorial objects, such as plane partitions, alternating sign matrices, and lattice paths
  • The Stanley formula expresses the number of reduced words for a permutation in terms of standard Young tableaux
• In the theory of symmetric functions, Schur functions serve as a fundamental basis and are connected to other important bases, such as monomial, power-sum, and elementary symmetric functions through transition matrices
• In quantum computing, Schur-Weyl duality is used to study the representation theory of the unitary group and its connection to quantum error correction codes
• In statistical mechanics, Schur functions appear in the study of integrable systems, such as the Toda lattice and the KP hierarchy
• In random matrix theory, Schur functions are used to describe the eigenvalue distribution of certain random matrix ensembles, such as the Wishart-Laguerre ensemble

Advanced Topics and Current Research

• The Kazhdan-Lusztig theory provides a geometric interpretation of the representation theory of Hecke algebras and the computation of Kazhdan-Lusztig polynomials using the Bruhat order on the symmetric group
• The Knutson-Tao puzzles give a combinatorial interpretation of the Littlewood-Richardson coefficients in terms of triangular puzzles, which has connections to Belkale-Kumar coefficients and the cohomology of flag varieties
• The Fomin-Kirillov algebra, also known as the Yang-Baxter algebra, is a quadratic algebra that generalizes the Bruhat order on the symmetric group and has applications in the study of Schubert polynomials and Grothendieck polynomials
• The theory of crystal bases, developed by Kashiwara, provides a combinatorial framework for studying representations of quantum groups and their connections to tableaux and Schur functions
• The Macdonald polynomials are a two-parameter generalization of Schur functions that have deep connections to affine Hecke algebras, double affine Hecke algebras, and the Macdonald-Koornwinder theory
• The study of $k$-Schur functions and affine Schur functions has led to new developments in the combinatorics of cores and quotients, as well as connections to the affine Grassmannian and the Peterson isomorphism
• The equivariant cohomology of Grassmannians and flag varieties has been a subject of intense research, with connections to Schubert calculus, quantum cohomology, and the geometry of Shimura varieties
• The asymptotic behavior of Kostka numbers and Littlewood-Richardson coefficients has been studied using techniques from representation theory, algebraic geometry, and random matrix theory, leading to new results on their growth rates and limiting distributions