CO 431: Symmetric Functions
Kevin Purbhoo
Estimated study time: 3 hr 16 min
Table of contents
Sources and References
Primary textbook — Richard P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999 (Chapter 7: Symmetric Functions — the definitive reference).
Supplementary texts — Bruce E. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd ed., Springer, 2001; Ian G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, 1995; William Fulton, Young Tableaux, Cambridge University Press, 1997; Sergey Fomin, “Symmetric Functions and the Theory of Combinatorial Identities,” MIT lecture notes.
Online resources — SAGE/SageMath symmetric functions module (doc.sagemath.org); FindStat database (findstat.org); OEIS sequences for symmetric function coefficients; Stephanie van Willigenburg, “Symmetric Functions” (UBC lecture notes, freely available).
Chapter 1: Partitions and Young Diagrams
The theory of symmetric functions rests on the combinatorics of integer partitions. A partition of a non-negative integer \( n \) is a weakly decreasing sequence \( \lambda = (\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_k > 0) \) of positive integers summing to \( n \). We write \( |\lambda| = \sum_i \lambda_i = n \) and say \( \lambda \vdash n \). The number of parts is \( \ell(\lambda) = k \), and the number of partitions of \( n \) is denoted \( p(n) \). Euler showed the generating function satisfies
\[ \sum_{n \geq 0} p(n) q^n = \prod_{k \geq 1} \frac{1}{1 - q^k}, \]a product that encodes the independent choices of how many times each part size appears. The resulting pentagonal number theorem gives a beautiful recursive formula for \( p(n) \).
The Young (Ferrers) diagram of \( \lambda \) is the left-justified array of boxes with \( \lambda_i \) boxes in row \( i \). Two notations are common: English notation places row 1 at the top, while French notation places it at the bottom. We work primarily in English notation. The conjugate partition \( \lambda' \) is obtained by reflecting across the main diagonal; explicitly, the \( j \)-th part of \( \lambda' \) counts the number of rows of \( \lambda \) with at least \( j \) boxes. It satisfies \( (\lambda')' = \lambda \).
Partitions of the same integer can be compared via the dominance order: \( \lambda \geq_{\mathrm{dom}} \mu \) if and only if \( \sum_{i \leq k} \lambda_i \geq \sum_{i \leq k} \mu_i \) for all \( k \geq 1 \). This partial order on partitions of \( n \) plays a fundamental role in the positivity properties of change-of-basis matrices.
- \( (4) \geq (3,1) \): partial sums \( 4 \geq 3 \), \( 4 \geq 4 \). Yes.
- \( (3,1) \geq (2,2) \): partial sums \( 3 \geq 2 \), \( 4 \geq 4 \). Yes.
- \( (3,1) \geq (2,1,1) \): partial sums \( 3 \geq 2 \), \( 4 \geq 3 \), \( 4 \geq 4 \). Yes.
- \( (2,2) \geq (2,1,1) \): partial sums \( 2 \geq 2 \), \( 4 \geq 3 \), \( 4 \geq 4 \). Yes.
- \( (2,1,1) \geq (1,1,1,1) \): partial sums \( 2 \geq 1 \), \( 3 \geq 2 \), \( 4 \geq 3 \), \( 4 \geq 4 \). Yes.
- \( (2,2) \) vs \( (3,1) \): \( (3,1) \geq (2,2) \) since \( 3 \geq 2 \) and \( 4 = 4 \), and not the reverse.
The resulting dominance order for \( n = 4 \) is the chain \( (4) >_{\mathrm{dom}} (3,1) >_{\mathrm{dom}} (2,2) >_{\mathrm{dom}} (2,1,1) >_{\mathrm{dom}} (1,1,1,1) \). For \( n = 4 \), this happens to be a total order; for larger \( n \) the dominance order is a genuine partial order with incomparable elements (for instance among partitions of 6, \( (3,2,1) \) and \( (3,3) \) are incomparable).
For a box \( (i, j) \in \lambda \), the hook length is \( h(i,j) = \lambda_i - j + \lambda'_j - i + 1 \), counting the box itself plus those directly to its right and directly below it in the diagram.
Hook lengths at each box:
- Box \( (1,1) \): \( h = \lambda_1 - 1 + \lambda'_1 - 1 + 1 = 3 - 1 + 3 - 1 + 1 = 5 \).
- Box \( (1,2) \): \( h = \lambda_1 - 2 + \lambda'_2 - 1 + 1 = 3 - 2 + 2 - 1 + 1 = 3 \).
- Box \( (1,3) \): \( h = \lambda_1 - 3 + \lambda'_3 - 1 + 1 = 3 - 3 + 1 - 1 + 1 = 1 \).
- Box \( (2,1) \): \( h = \lambda_2 - 1 + \lambda'_1 - 2 + 1 = 2 - 1 + 3 - 2 + 1 = 3 \).
- Box \( (2,2) \): \( h = \lambda_2 - 2 + \lambda'_2 - 2 + 1 = 2 - 2 + 2 - 2 + 1 = 1 \).
- Box \( (3,1) \): \( h = \lambda_3 - 1 + \lambda'_1 - 3 + 1 = 1 - 1 + 3 - 3 + 1 = 1 \).
Product of hook lengths: \( 5 \cdot 3 \cdot 1 \cdot 3 \cdot 1 \cdot 1 = 45 \). Therefore
\[ f^{(3,2,1)} = \frac{6!}{45} = \frac{720}{45} = 16. \]There are exactly 16 standard Young tableaux of shape \( (3,2,1) \). One can verify this is consistent with the representation theory: \( V^{(3,2,1)} \) is a 16-dimensional irreducible \( S_6 \)-module, and \( \sum_{\lambda \vdash 6} (f^\lambda)^2 = 6! = 720 \) (each \( (f^\lambda)^2 \) contributing, with 16 being the largest single contribution).
A semistandard Young tableau (SSYT) of shape \( \lambda \) is a filling of the Young diagram with positive integers that is weakly increasing along each row and strictly increasing down each column. The content (or weight) of a tableau \( T \) is the vector \( \mu \) where \( \mu_i \) counts the number of \( i \)’s appearing in \( T \). The Kostka number \( K_{\lambda\mu} \) counts the SSYT of shape \( \lambda \) and content \( \mu \). A standard Young tableau (SYT) is the special case where the entries are exactly \( \{1, \ldots, n\} \), each appearing once; equivalently, \( K_{\lambda, (1^n)} = f^\lambda \).
Enumerating valid triples \( (a, b, c) \) with \( \{a,b,c\} = \{1,2,3\} \) and \( a < b \), \( c > a \):
- \( (a,b,c) = (1,2,3) \): \( c = 3 > 1 = a \). Valid. Tableau: row 1 is \( 1\ 2 \), row 2 is \( 3 \).
- \( (a,b,c) = (1,3,2) \): \( c = 2 > 1 = a \). Valid. Tableau: row 1 is \( 1\ 3 \), row 2 is \( 2 \).
- \( (a,b,c) = (2,3,1) \): \( c = 1 > 2 = a \)? No. Invalid.
Therefore \( K_{(2,1),(1,1,1)} = 2 \), confirming that \( f^{(2,1)} = 2 \) (two standard Young tableaux of shape \( (2,1) \)). This is also consistent with the hook-length formula: hooks of \( (2,1) \) are \( h(1,1) = 3, h(1,2) = 1, h(2,1) = 1 \), giving \( f^{(2,1)} = 3!/(3 \cdot 1 \cdot 1) = 6/3 = 2 \). \( \checkmark \)
We now compute the hook length \( h(i,j) = \lambda_i - j + \lambda'_j - i + 1 \) for each of the 7 boxes.
Row 1 (\( \lambda_1 = 4 \)):
- Box \( (1,1) \): \( h = 4 - 1 + 3 - 1 + 1 = 6 \).
- Box \( (1,2) \): \( h = 4 - 2 + 2 - 1 + 1 = 4 \).
- Box \( (1,3) \): \( h = 4 - 3 + 1 - 1 + 1 = 2 \).
- Box \( (1,4) \): \( h = 4 - 4 + 1 - 1 + 1 = 1 \).
Row 2 (\( \lambda_2 = 2 \)):
- Box \( (2,1) \): \( h = 2 - 1 + 3 - 2 + 1 = 3 \).
- Box \( (2,2) \): \( h = 2 - 2 + 2 - 2 + 1 = 1 \).
Row 3 (\( \lambda_3 = 1 \)):
- Box \( (3,1) \): \( h = 1 - 1 + 3 - 3 + 1 = 1 \).
Arranging these in the Young diagram (English notation):
\[ \begin{array}{|c|c|c|c|} \hline 6 & 4 & 2 & 1 \\ \hline 3 & 1 & & \\ \hline 1 & & & \\ \hline \end{array} \]Product of all hook lengths: \( 6 \cdot 4 \cdot 2 \cdot 1 \cdot 3 \cdot 1 \cdot 1 = 144 \). Therefore:
\[ f^{(4,2,1)} = \frac{7!}{144} = \frac{5040}{144} = 35. \]There are exactly 35 standard Young tableaux of shape \( (4,2,1) \). As a sanity check: summing \( (f^\lambda)^2 \) over all \( \lambda \vdash 7 \) must equal \( 7! = 5040 \). The 15 partitions of 7 contribute \( f^{(7)} = 1 \), \( f^{(6,1)} = 6 \), \( f^{(5,2)} = 14 \), \( f^{(5,1,1)} = 15 \), \( f^{(4,3)} = 14 \), \( f^{(4,2,1)} = 35 \), and so on. The shape \( (4,2,1) \) contributes \( 35^2 = 1225 \), which is the largest single contribution among all \( \lambda \vdash 7 \), consistent with \( (4,2,1) \) being a “central” shape for \( n = 7 \).
Hook lengths:
- \( h(1,1) = 3-1+2-1+1 = 4 \).
- \( h(1,2) = 3-2+2-1+1 = 3 \).
- \( h(1,3) = 3-3+1-1+1 = 1 \).
- \( h(2,1) = 2-1+2-2+1 = 2 \).
- \( h(2,2) = 2-2+2-2+1 = 1 \).
Product: \( 4 \cdot 3 \cdot 1 \cdot 2 \cdot 1 = 24 \). So \( f^{(3,2)} = 120/24 = 5 \). There are exactly 5 SYT of shape \( (3,2) \). Let us list all of them explicitly. Each tableau fills the 5 boxes with \( \{1,2,3,4,5\} \), increasing along rows and down columns. Entries in row 1 occupy columns 1–3 and entries in row 2 occupy columns 1–2.
The entry in box \( (2,1) \) must be greater than box \( (1,1) \), and box \( (2,2) \) must be greater than both \( (1,2) \) and \( (2,1) \). The 5 tableaux are:
\[ \begin{array}{|c|c|c|} \hline 1 & 2 & 3 \\\hline 4 & 5 & \\\hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 2 & 4 \\\hline 3 & 5 & \\\hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 2 & 5 \\\hline 3 & 4 & \\\hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 3 & 4 \\\hline 2 & 5 & \\\hline \end{array} \quad \begin{array}{|c|c|c|} \hline 1 & 3 & 5 \\\hline 2 & 4 & \\\hline \end{array} \]One can verify these are the only 5 by noting that box \( (1,1) \) must contain 1 (it is the smallest possible entry and must be smaller than everything to its right and below). Then box \( (2,1) \) can be 2, 3, or 4 (but constrained by what follows), giving the branching that produces exactly 5 completions.
The formula has deep connections beyond combinatorics. Via the RSK correspondence, the Plancherel measure on partitions of \( n \) assigns probability \( (f^\lambda)^2/n! \) to each \( \lambda \vdash n \). The distribution of the largest part \( \lambda_1 \) under Plancherel measure equals the distribution of the length of the longest increasing subsequence (LIS) of a uniform random permutation in \( S_n \). By the Baik-Deift-Johansson theorem (1999), after centering by \( 2\sqrt{n} \) and scaling by \( n^{1/6} \), this converges in distribution to the Tracy-Widom GUE distribution — the same distribution that governs the largest eigenvalue of a random Gaussian Unitary Ensemble matrix. This is one of the most striking instances of universality in modern probability.
Let us check all potentially comparable pairs, beginning from the top.
- \( (5) \geq (4,1) \): partial sums \( 5 \geq 4 \), \( 5 \geq 5 \). ✓ Comparable.
- \( (4,1) \geq (3,2) \): \( 4 \geq 3 \), \( 5 \geq 5 \). ✓
- \( (4,1) \geq (3,1,1) \): \( 4 \geq 3 \), \( 5 \geq 4 \), \( 5 \geq 5 \). ✓
- \( (3,2) \geq (3,1,1) \): \( 3 \geq 3 \), \( 5 \geq 4 \), \( 5 \geq 5 \). ✓
- \( (3,2) \) vs \( (2,2,1) \): compare partial sums \( (3,5,5) \) vs \( (2,4,5) \). At every step \( 3 \geq 2 \), \( 5 \geq 4 \), \( 5 \geq 5 \). ✓ So \( (3,2) \geq (2,2,1) \).
- \( (3,1,1) \) vs \( (2,2,1) \): partial sums \( (3,4,5) \) vs \( (2,4,5) \). At step 1: \( 3 \geq 2 \) ✓; step 2: \( 4 \geq 4 \) ✓; step 3: \( 5 \geq 5 \) ✓. So \( (3,1,1) \geq (2,2,1) \).
- \( (2,2,1) \geq (2,1,1,1) \): partial sums \( (2,4,5) \) vs \( (2,3,4,5) \). ✓
- \( (2,1,1,1) \geq (1^5) \): ✓ by first partial sum \( 2 \geq 1 \).
The potentially incomparable pairs are \( \{(3,2),(3,1,1)\} \) — but we just showed \( (3,2) \geq (3,1,1) \) — and no other pairs turn out to be incomparable for \( n=5 \). In fact the dominance order on partitions of 5 is a total order:
\[ (5) >_{\mathrm{dom}} (4,1) >_{\mathrm{dom}} (3,2) >_{\mathrm{dom}} (3,1,1) >_{\mathrm{dom}} (2,2,1) >_{\mathrm{dom}} (2,1,1,1) >_{\mathrm{dom}} (1^5). \]Dominance first becomes a genuine partial order (with incomparable elements) at \( n = 6 \): the partitions \( (3,2,1) \) and \( (4,1,1) \) satisfy partial sums \( (3,5,6) \) vs \( (4,5,6) \), giving \( (4,1,1) \geq (3,2,1) \); but \( (3,3) \) vs \( (4,1,1) \): sums \( (3,6) \) vs \( (4,5,6) \) — at step 1 we have \( 3 < 4 \), so \( (3,3) \not\geq (4,1,1) \); at step 2 we have \( 6 = 6 \) but step 1 already fails in the other direction too, since \( 4 > 3 \) means \( (4,1,1) \not\leq (3,3) \). So \( (3,3) \) and \( (4,1,1) \) are incomparable under dominance order for \( n = 6 \).
| Term | Definition |
|---|---|
| \( \lambda \vdash n \) | Integer partition of \( n \) |
| \( \ell(\lambda) \) | Number of parts |
| \( \lambda' \) | Conjugate partition |
| \( K_{\lambda\mu} \) | Kostka number: #SSYT of shape \( \lambda \), content \( \mu \) |
| \( f^\lambda \) | Number of SYT of shape \( \lambda \) |
Chapter 2: The Ring of Symmetric Functions
Why study symmetric polynomials? The most elementary reason is that they arise naturally whenever the individual variables are interchangeable: the characteristic polynomial of a matrix has coefficients that are symmetric in the eigenvalues, the Vieta formulas express the coefficients of \( (x-r_1)\cdots(x-r_n) \) symmetrically in the roots \( r_i \), and any quantity intrinsic to a set of numbers (their sum, sum of squares, product) must be symmetric. More deeply, symmetric functions form the universal language for simultaneously describing how combinatorial objects (tableaux, permutations, lattice paths) and algebraic objects (representations of \( S_n \), polynomial representations of \( \mathrm{GL}(n) \)) depend on a collection of variables — a dependence that respects no ordering among the variables.
The ring \( \Lambda \) has several natural bases, each adapted to a different context. The elementary symmetric functions \( e_\lambda \) appear in characteristic polynomials and Vieta’s formulas; the complete homogeneous functions \( h_\lambda \) arise in plethysm and in the theory of Hall polynomials; the power sums \( p_\lambda \) are the natural characters of one-dimensional representations; and the monomial functions \( m_\lambda \) are the “atomic” symmetric functions with one term type. The reason there are multiple bases — rather than just one — is that each illuminates a different aspect of the theory, and the change-of-basis matrices between them (Kostka numbers, character tables) carry deep combinatorial and algebraic information. Schur functions, introduced at the end of this chapter, are in some sense the “right” basis for all purposes simultaneously.
A polynomial \( f \in \mathbb{Z}[x_1, \ldots, x_n] \) is symmetric if \( f(x_{\sigma(1)}, \ldots, x_{\sigma(n)}) = f(x_1, \ldots, x_n) \) for every permutation \( \sigma \in S_n \). The symmetric polynomials form a subring \( \Lambda_n = \mathbb{Z}[x_1, \ldots, x_n]^{S_n} \). Passing to the inverse limit as \( n \to \infty \) yields the ring of symmetric functions
\[ \Lambda = \varprojlim_n \Lambda_n, \]whose elements are formal power series in infinitely many variables, symmetric under all finite permutations. The ring \( \Lambda \) is graded: \( \Lambda = \bigoplus_{n \geq 0} \Lambda^n \), where \( \Lambda^n \) consists of homogeneous symmetric functions of degree \( n \). The standard bases of \( \Lambda \) are indexed by partitions.
The monomial basis is the most elementary: by definition, \( m_\lambda \) contains exactly the monomials of “type \( \lambda \)” and no others, so any symmetric function can be written uniquely as an integer linear combination of the \( m_\lambda \). The coefficients in this expansion are completely determined by the coefficient of any single monomial of that type.
The two generating functions satisfy \( \left(\sum_k e_k t^k\right)\left(\sum_k h_k (-t)^k\right) = 1 \), since their product is \( \prod_i (1+x_i t) \cdot \prod_i \frac{1}{1+x_i t} = 1 \). Extracting the coefficient of \( t^n \) yields Newton’s identity:
\[ h_n - e_1 h_{n-1} + e_2 h_{n-2} - \cdots + (-1)^n e_n = 0. \]Observe that \( h_2 \) contains both “pure square” terms (from \( m_{(2)} \)) and “mixed” terms (from \( m_{(1,1)} = e_2 \)), reflecting the identity \( h_2 = m_{(2)} + e_2 \) in 3 or more variables.
- \( h_3 = m_{(3)} + m_{(2,1)} + m_{(1,1,1)} \).
- \( e_1 h_2 = m_{(1)} \cdot (m_{(2)} + m_{(1,1)}) = m_{(3)} + 2m_{(2,1)} + m_{(1,1,1)} \).
- \( e_2 h_1 \): we have \( e_2 = m_{(1,1)} \) and \( h_1 = m_{(1)} \), so \( e_2 h_1 = (x_1 x_2 + x_1 x_3 + x_2 x_3)(x_1 + x_2 + x_3) = m_{(2,1)} + m_{(1,1,1)} \).
- \( e_3 = x_1 x_2 x_3 = m_{(1,1,1)} \).
Each monomial type cancels exactly.
The involution \( \omega : \Lambda \to \Lambda \) is the algebra map defined by \( \omega(e_k) = h_k \) (equivalently, \( \omega(h_k) = e_k \)). It satisfies \( \omega^2 = \mathrm{id} \) and \( \omega(p_\lambda) = \varepsilon(\lambda) p_\lambda \) where \( \varepsilon(\lambda) = (-1)^{|\lambda| - \ell(\lambda)} \) is the sign of a permutation of cycle type \( \lambda \). The involution \( \omega \) is a graded algebra isomorphism that recurs throughout the theory.
For example, take \( \lambda = (3,1) \vdash 4 \). Its conjugate is \( \lambda' = (2,1,1) \): the diagram of \( (3,1) \) has columns of lengths 2, 1, 1 (reading from left), giving \( \lambda' = (2,1,1) \). So \( \omega(s_{(3,1)}) = s_{(2,1,1)} \).
The partition \( (2,1) \) is self-conjugate (its diagram is symmetric across the diagonal), so \( \omega(s_{(2,1)}) = s_{(2,1)} \) — this Schur function is fixed by \( \omega \). Self-conjugate partitions correspond precisely to the representations that are “fixed” by the outer automorphism of \( S_n \) given by tensoring with the sign representation.
There are exactly 3 monomials, corresponding to choosing which variable receives the exponent 2 (the remaining two each receive exponent 1). In 4 or more variables, \( m_{(2,1,1)} \) would also include terms like \( x_1^2 x_2 x_4, x_1 x_2^2 x_4, \ldots \) and so on.
Contrast with \( m_{(2,2)} \) in 3 variables: here the exponents are \( \{2,2\} \), to be placed on 2 of the 3 variables with the third getting 0. So \( m_{(2,2)} = x_1^2 x_2^2 + x_1^2 x_3^2 + x_2^2 x_3^2 \) — 3 monomials from choosing which 2 of the 3 variables receive the exponent 2.
In \( n < 3 \) variables, \( e_3 = 0 \) (cannot choose 3 distinct indices). In \( n \geq 4 \) variables, \( e_3 \) acquires more terms.
\[ h_3(x_1,x_2,x_3) = x_1^3 + x_2^3 + x_3^3 + x_1^2 x_2 + x_1^2 x_3 + x_1 x_2^2 + x_2^2 x_3 + x_1 x_3^2 + x_2 x_3^2 + x_1 x_2 x_3. \]In terms of monomial symmetric functions: \( h_3 = m_{(3)} + m_{(2,1)} + m_{(1,1,1)} \). Explicitly, \( m_{(3)} = x_1^3 + x_2^3 + x_3^3 \) (3 terms), \( m_{(2,1)} = x_1^2 x_2 + x_1^2 x_3 + x_1 x_2^2 + x_2^2 x_3 + x_1 x_3^2 + x_2 x_3^2 \) (6 terms), and \( m_{(1,1,1)} = x_1 x_2 x_3 \) (1 term), for a total of 10 monomials — consistent with \( \binom{3+3-1}{3} = 10 \) weakly increasing triples from \( \{1,2,3\} \).
We have:
\[ e_1 = x_1 + x_2, \quad e_2 = x_1 x_2, \quad h_1 = x_1 + x_2, \quad h_2 = x_1^2 + x_1 x_2 + x_2^2. \]Computing the right-hand side:
\[ e_1 h_1 - e_2 = (x_1 + x_2)^2 - x_1 x_2 = x_1^2 + 2x_1 x_2 + x_2^2 - x_1 x_2 = x_1^2 + x_1 x_2 + x_2^2 = h_2. \quad \checkmark \]The key observation is that \( e_1 h_1 = (x_1 + x_2)^2 = h_1^2 \) overcounts the cross-term \( x_1 x_2 \) twice (once as \( x_1 \cdot x_2 \) and once as \( x_2 \cdot x_1 \)), while \( h_2 \) counts \( x_1 x_2 \) only once. Subtracting \( e_2 = x_1 x_2 \) corrects this overcounting. This is a combinatorial explanation of the algebraic identity.
- \( K_{(3),(3)} = 1 \): the unique SSYT of shape \( (3) \) with content \( (3) \) has all entries equal to 1: \( \boxed{1\ 1\ 1} \).
- \( K_{(3),(2,1)} = 1 \): content \( (2,1) \) means two 1's and one 2. Row-weakly-increasing forces \( \boxed{1\ 1\ 2} \). One tableau.
- \( K_{(3),(1,1,1)} = 1 \): content \( (1,1,1) \) forces \( \boxed{1\ 2\ 3} \). One SYT.
- \( K_{(2,1),(3)} = 0 \): content \( (3) \) means all entries are 1, but column-strictness requires row 2 entry \( > \) row 1 entry in column 1. Impossible with all 1's. Zero tableaux.
- \( K_{(2,1),(2,1)} = 1 \): content \( (2,1) \) (two 1's, one 2). Row 1 must be weakly increasing, column 1 must be strictly increasing. The only filling: row 1 is \( 1\ 2 \), row 2 is \( 1 \). Verify: row 1 weakly increasing ✓, column 1 has entries 1 (row 1) and 1 (row 2) — wait, column strictness requires 1 \( < \) 1, which fails. Try row 1 is \( 1\ 1 \), row 2 is \( 2 \): column 1 has 1 and 2 with \( 1 < 2 \) ✓, row 1 weakly increasing ✓. One valid tableau.
- \( K_{(2,1),(1,1,1)} = 2 \): the two SYT of shape \( (2,1) \) are \( \{1\ 2 / 3\} \) and \( \{1\ 3 / 2\} \) (row 1 / row 2). Both verified earlier.
- \( K_{(1,1,1),(3)} = 0 \), \( K_{(1,1,1),(2,1)} = 0 \): for shape \( (1,1,1) \) (a single column of 3), column-strictness requires all entries strictly increasing. Content \( (3) \) or \( (2,1) \) would require a repeated entry. Zero tableaux.
- \( K_{(1,1,1),(1,1,1)} = 1 \): the unique SYT of shape \( (1,1,1) \) is \( 1 / 2 / 3 \) (column with entries 1, 2, 3 from top).
The Kostka matrix for \( n = 3 \) is therefore:
\[ K = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}. \]This is upper unitriangular with respect to dominance order (entries below the diagonal are zero, diagonal entries are all 1). Upper triangularity reflects the fundamental fact that \( K_{\lambda\mu} = 0 \) unless \( \lambda \geq_{\mathrm{dom}} \mu \), and \( K_{\lambda\lambda} = 1 \) (there is exactly one SSYT of shape \( \lambda \) and content \( \lambda \), obtained by filling the \( i \)-th row with all \( i \)’s).
The matrix expressing \( s_\lambda \) in the \( m \)-basis is the Kostka matrix \( K \) computed above. The matrix expressing \( m_\lambda \) in the \( h \)-basis has \( (M_h)_{\lambda\mu} \) equal to the number of matrices with non-negative integer entries whose row sums form \( \lambda \) and column sums form \( \mu \) — since \( h_\mu = h_{\mu_1} h_{\mu_2} \cdots \) and \( h_k = \sum_{|\nu|=k} m_\nu \), expanding the product counts such matrices. For \( n=3 \):
\[ h_{(3)} = m_{(3)} + m_{(2,1)} + m_{(1,1,1)}, \quad h_{(2,1)} = h_2 h_1 = (m_{(2)}+m_{(1,1)}) \cdot m_{(1)}. \]Expanding \( h_2 h_1 \) in the monomial basis: \( m_{(2)} \cdot m_{(1)} = m_{(3)} + m_{(2,1)} \) and \( m_{(1,1)} \cdot m_{(1)} = m_{(2,1)} + m_{(1,1,1)} \) (up to multinomial coefficients from orbit sizes). The transition matrix from any basis to any other can be computed from these elementary expansions, and each entry has a combinatorial interpretation.
Why are the four bases \( m, e, h, p \) not enough? Each one is “one-dimensional” as a representation-theoretic object: the power sums \( p_\lambda \) compute character values but only after dividing by \( z_\lambda \); the \( e \) and \( h \) bases are polynomial generators but are not orthogonal under the natural inner product; and \( m_\lambda \) lacks good positivity properties. Schur functions solve all of these problems simultaneously: they are orthonormal under the Hall inner product, they expand with non-negative integer coefficients in any classical basis (positivity), and their Frobenius image is exactly the character of an irreducible \( S_n \)-representation. This triple coincidence — combinatorial, algebraic, and representation-theoretic — is what makes Schur functions the central basis.
- \( a=1, b=1, c=2 \): row \( 1 \leq 1 \) ✓, column \( 2 > 1 \) ✓. Weight \( x_1^2 x_2 \).
- \( a=1, b=2, c=2 \): row \( 1 \leq 2 \) ✓, column \( 2 > 1 \) ✓. Weight \( x_1 x_2^2 \).
We can cross-check: \( s_{(2,1)} = m_{(2,1)} + 2m_{(1,1,1)} \) in general, and in 2 variables \( m_{(1,1,1)} = 0 \) (no three distinct indices available), so \( s_{(2,1)}(x_1,x_2) = m_{(2,1)}(x_1,x_2) = x_1^2 x_2 + x_1 x_2^2 \). \( \checkmark \)
Chapter 3: Schur Functions and the Jacobi-Trudi Identity
The combinatorial definition of Schur functions as generating functions over SSYT (Chapter 2) is beautiful and directly connects to Kostka numbers, but it is poorly suited for algebraic manipulations: computing products, expressing a Schur function in the \( h \)- or \( e \)-basis, or proving the Cauchy identity all become combinatorial gauntlets. The Jacobi-Trudi identity provides the algebraic definition, expressing each \( s_\lambda \) as a determinant in the complete homogeneous functions \( h_k \). Determinants interact well with algebra — they satisfy Plücker relations, they change predictably under row operations, and they encode non-intersecting lattice path configurations via the Lindström-Gessel-Viennot lemma. The payoff is a toolkit for computing in \( \Lambda \) that is both explicit and mechanically powerful.
Both identities are proved via the Lindström-Gessel-Viennot (LGV) lemma, which interprets a determinant of path-counting generating functions as the signed sum over tuples of non-intersecting lattice paths. SSYT of shape \( \lambda \) biject with non-intersecting lattice path families, and the sign of each path tuple is always \( +1 \), so the determinant equals the count.
Then \( h_1 h_2 = x_1^3 + 2x_1^2 x_2 + 2x_1 x_2^2 + x_2^3 \), and
\[ h_1 h_2 - h_3 = x_1^2 x_2 + x_1 x_2^2, \]matching \( s_{(2,1)}(x_1,x_2) = x_1^2 x_2 + x_1 x_2^2 \) computed from SSYT. \( \checkmark \)
The Pieri rules describe multiplication of a Schur function by a complete homogeneous or elementary symmetric function.
where the sum is over all \( \nu \supseteq \lambda \) with \( |\nu| = |\lambda| + n \) such that \( \nu/\lambda \) is a vertical strip (at most one new box per row).
- \( \mu = (4) \): new boxes at \( (1,3),(1,4) \) — different columns, same row. Horizontal strip ✓.
- \( \mu = (3,1) \): new boxes at \( (1,3),(2,1) \) — columns 3 and 1, different. Horizontal strip ✓.
- \( \mu = (2,2) \): new boxes at \( (2,1),(2,2) \) — columns 1 and 2, different. Horizontal strip ✓.
- \( \mu = (2,1,1) \): new boxes at \( (2,1),(3,1) \) — both in column 1! Not a horizontal strip. ✗
Step 1: Path model for \( h_k \). Interpret \( h_k \) as the generating function for lattice paths from \( A = (0,0) \) to \( B = (k, 0) \) taking steps \( (1, 0) \) (labelled by a variable \( x_i \) with multiplicity) or \( (0, 1) \) then \( (0,-1) \). More precisely, use paths in \( \mathbb{Z}^2 \) from the source \( a_i = (1-i, 0) \) to the sink \( b_j = (\lambda_j - j + 1, 0) \), where each path carries the weight equal to the product of variables at each horizontal step. The generating function for a single path from \( (0,0) \) to \( (k,0) \) in this model is exactly \( h_k \), since the weakly increasing monomials of degree \( k \) correspond to ordered sequences of horizontal steps.
\[ \det(e(a_i, b_j))_{i,j} = \sum_{\text{non-intersecting path tuples}} \mathrm{sgn}(\sigma) \cdot \mathrm{wt}(P), \]where the sum is over \( \ell \)-tuples of paths \( P_i \) from \( a_i \) to \( b_{\sigma(i)} \), weighted by the product of path weights, and intersecting tuples cancel in signed pairs.
Step 3: Bijection with SSYT. In the specific path model for the Jacobi-Trudi identity, the non-intersecting path tuples (going from sources \( a_i = (1-i, 0) \) to sinks \( b_i = (\lambda_i - i + 1, 0) \) via the identity permutation \( \sigma = \mathrm{id} \)) are in weight-preserving bijection with SSYT of shape \( \lambda \). The \( i \)-th path encodes the \( i \)-th row of the SSYT: a horizontal step to column \( j \) labelled by \( x_k \) corresponds to a box in row \( i \) filled with \( k \). The non-intersection condition translates exactly to the column-strictness requirement of SSYT (if path \( i \) and path \( i+1 \) share a horizontal position, the entry in row \( i \) would equal the entry in row \( i+1 \), violating strict column increase).
Step 4: Signs vanish. In this specific path model, all non-intersecting path tuples correspond to \( \sigma = \mathrm{id} \) with sign \( +1 \), because the paths are forced to go from source \( a_i \) to sink \( b_i \) (any other matching leads to intersection). Therefore, all signs in the LGV determinant are \( +1 \), and the determinant equals the sum over non-intersecting path tuples, which is \( \sum_T x^{\mathrm{wt}(T)} = s_\lambda \). \( \square \)
The boxes of \( (3,1) \) occupy columns 1–3 in row 1 and column 1 in row 2. Adding 2 boxes as a horizontal strip:
- \( \mu = (5,1) \): add boxes \( (1,4),(1,5) \) — two new boxes in row 1, columns 4 and 5. Different columns. ✓
- \( \mu = (4,2) \): add boxes \( (1,4),(2,2) \) — columns 4 and 2. Different. ✓
- \( \mu = (4,1,1) \): add boxes \( (1,4),(3,1) \) — columns 4 and 1. Different. ✓
- \( \mu = (3,3) \): add boxes \( (2,2),(2,3) \) — columns 2 and 3 in row 2. Different. ✓
- \( \mu = (3,2,1) \): add boxes \( (2,2),(3,1) \) — columns 2 and 1. Different. ✓
- \( \mu = (3,1,1,1) \): add boxes \( (3,1),(4,1) \) — both in column 1! Not a horizontal strip. ✗
- \( \mu = (3,1,2) \): this would not be a partition (parts not weakly decreasing).
Therefore:
\[ s_{(3,1)} \cdot h_2 = s_{(5,1)} + s_{(4,2)} + s_{(4,1,1)} + s_{(3,3)} + s_{(3,2,1)}. \]Each valid outer shape contributes with coefficient 1, reflecting \( c^\mu_{(3,1),(2)} \in \{0,1\} \) for horizontal strips (a special case of the Pieri rule, which recovers the LR rule with \( \nu = (2) \)).
The shape \( \lambda = (2,1) \) has corners (positions where we can begin adding a strip) at \( (1,3) \) (end of row 1) and \( (2,2) \) (would extend row 2) and \( (3,1) \) (new row). Let us enumerate all border strips of size 2:
- Strip in row 1 only: add boxes \( (1,3),(1,4) \) — horizontal domino in row 1. New shape: \( (4,1) \). Height: \( 1 - 1 = 0 \). Sign: \( (-1)^0 = +1 \). Contribution: \( +s_{(4,1)} \).
- Strip spanning rows 1 and 2: add boxes \( (1,3),(2,2) \) — one box at end of row 1 and one at end of row 2. This is a connected skew shape (the box \( (2,2) \) is directly below \( (1,2) \) which borders \( (1,3) \)), with no \( 2 \times 2 \) block. New shape: \( (3,2) \). Height: \( 2-1 = 1 \). Sign: \( -1 \). Contribution: \( -s_{(3,2)} \).
- Strip in row 2 only: to add two boxes in row 2 alone starting from \( (2,2),(2,3) \) — but the existing row 2 only has 1 box at \( (2,1) \), and a horizontal domino at \( (2,2),(2,3) \) would give shape \( (2,3) \) which is not a valid partition (parts must be weakly decreasing). ✗
- Strip spanning rows 2 and 3: add boxes \( (2,2),(3,1) \) — one at end of row 2, one in new row 3. Connected (they share column adjacency via \( (2,1) \)-(3,1)). New shape: \( (2,2,1) \). Height: \( 2-1 = 1 \). Sign: \( -1 \). Contribution: \( -s_{(2,2,1)} \).
- Strip in new rows 3 and 4: add boxes \( (3,1),(4,1) \) — vertical domino below row 2. Connected. New shape: \( (2,1,1,1) \). Height: 1. Sign: \( -1 \). Contribution: \( -s_{(2,1,1,1)} \).
Therefore:
\[ p_2 \cdot s_{(2,1)} = s_{(4,1)} - s_{(3,2)} - s_{(2,2,1)} - s_{(2,1,1,1)}. \]One can verify this using the Jacobi-Trudi identity and Newton’s identity \( p_2 = h_1 p_1 - 2 h_2 + 2 h_1^2 - \ldots \), but the Murnaghan-Nakayama rule gives the answer directly by a combinatorial procedure.
The Murnaghan-Nakayama rule handles multiplication by power sums. A border strip (or ribbon) of size \( n \) is a connected skew shape containing no \( 2 \times 2 \) square. Its height is \( \mathrm{ht}(R) = (\text{number of rows occupied}) - 1 \). Then
\[ s_\lambda \cdot p_n = \sum_{R} (-1)^{\mathrm{ht}(R)} s_{\lambda \cup R}, \]summed over border strips \( R \) of size \( n \) that can be added to \( \lambda \). This rule is powerful for computing character values of \( S_n \), as we will see in Chapter 6.
- Horizontal domino extending row 1: shape \( (5,1) \), strip in 1 row, \( \mathrm{ht}=0 \), sign \( +1 \).
- Vertical domino in columns 3 and 4: shape \( (4,2) \), strip in 2 rows, \( \mathrm{ht}=1 \), sign \( -1 \).
- Horizontal domino extending row 2: shape \( (3,3) \), strip in 1 row, \( \mathrm{ht}=0 \), sign \( +1 \).
- Vertical domino going into rows 2 and 3: shape \( (3,2,1) \), strip in 2 rows, \( \mathrm{ht}=1 \), sign \( -1 \).
- Vertical domino in rows 3 and 4: shape \( (3,1,1,1) \), strip in 2 rows, \( \mathrm{ht}=1 \), sign \( -1 \).
Skew shapes. For \( \mu \subseteq \lambda \) (meaning \( \mu_i \leq \lambda_i \) for all \( i \)), the skew shape \( \lambda/\mu \) is the set of boxes in \( \lambda \) but not \( \mu \). The skew Schur function is defined by the skew Jacobi-Trudi identity:
\[ s_{\lambda/\mu} = \det\bigl(h_{\lambda_i - \mu_j - i + j}\bigr)_{1 \leq i,j \leq \ell(\lambda)}, \]or equivalently as \( s_{\lambda/\mu} = \sum_T x^{\mathrm{wt}(T)} \) over SSYT of skew shape \( \lambda/\mu \). Crucially, the skew Schur functions expand in the Schur basis as
\[ s_{\lambda/\mu} = \sum_\nu c^\lambda_{\mu\nu} s_\nu, \]where \( c^\lambda_{\mu\nu} \) are the Littlewood-Richardson coefficients, the subject of Chapter 7.
Chapter 4: The Hall Inner Product and Dual Bases
The Hall inner product is introduced to give the ring of symmetric functions a notion of orthogonality that reflects the duality between the \( h \) and \( m \) bases — a duality that in turn descends from the pairing between polynomial representations and permutation representations in the representation theory of \( S_n \). Without this inner product, we would have no canonical way to isolate individual basis components or state the self-duality of Schur functions. With it, every expansion “find the coefficient of \( s_\nu \) in \( f \)” becomes a matter of computing \( \langle f, s_\nu \rangle \).
and \( m_i(\lambda) \) is the multiplicity of \( i \) as a part of \( \lambda \). Note that \( z_\lambda \) equals the order of the centralizer of a permutation of cycle type \( \lambda \) in \( S_n \), and \( n!/z_\lambda \) is the size of that conjugacy class.
The proof uses the unitriangularity of the Kostka matrix. We know \( s_\lambda = \sum_\nu K_{\lambda\nu} m_\nu \) and \( h_\mu = \sum_\nu K_{\nu\mu}^{-1} s_\nu \) (inverse Kostka, or equivalently \( s_\mu = \sum_\nu K_{\mu\nu} m_\nu \) and the dual expansion). Since \( \langle h_\lambda, m_\mu \rangle = \delta_{\lambda\mu} \), the transition matrix from \( s \) to \( m \) is \( K^T \) and the transition from \( s \) to \( h \) is \( K^{-1} \); these being transposes of one another implies \( \langle s_\lambda, s_\mu \rangle = \delta_{\lambda\mu} \).
The involution \( \omega \) is an isometry: \( \langle \omega(f), \omega(g) \rangle = \langle f, g \rangle \) for all \( f, g \in \Lambda \). One consequence is \( \omega(s_\lambda) = s_{\lambda'} \), relating Schur functions indexed by conjugate partitions.
The Cauchy identity encodes the orthonormality of Schur functions through a generating function in two sets of variables \( x = (x_1, x_2, \ldots) \) and \( y = (y_1, y_2, \ldots) \):
\[ \sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j \geq 1} \frac{1}{1 - x_i y_j} = \sum_\lambda h_\lambda(x) m_\lambda(y). \]Applying \( \omega_x \) (the involution in the \( x \)-variables) yields the dual Cauchy identity:
\[ \sum_\lambda s_\lambda(x) s_{\lambda'}(y) = \prod_{i,j \geq 1} (1 + x_i y_j). \]Step 1: Express \( s \) in \( m \) and \( h \) bases. We have \( s_\lambda = \sum_\nu K_{\lambda\nu} m_\nu \) by the SSYT definition of Schur functions, where \( K_{\lambda\nu} \) is the Kostka number. We also have \( h_\mu = \sum_\nu K_{\nu\mu} s_\nu \) (equivalently, \( s_\mu = \sum_\alpha (K^{-1})_{\mu\alpha} h_\alpha \) in the \( h \)-basis, but more usefully: \( h_\mu \) is expressed in the Schur basis with Kostka coefficients \( K_{\nu\mu} \)). This second identity follows from the general fact that \( K \) is the transition matrix both ways, using unitriangularity.
\[ \langle s_\lambda, s_\mu \rangle = \left\langle \sum_\nu K_{\lambda\nu} m_\nu,\ s_\mu \right\rangle. \]Now use \( s_\mu = \sum_\alpha (K^{-1})_{\mu\alpha} h_\alpha \) (which holds because \( K \) is invertible, being upper unitriangular):
\[ \langle s_\lambda, s_\mu \rangle = \sum_{\nu, \alpha} K_{\lambda\nu} (K^{-1})_{\mu\alpha} \langle m_\nu, h_\alpha \rangle = \sum_{\nu, \alpha} K_{\lambda\nu} (K^{-1})_{\mu\alpha} \delta_{\nu\alpha} = \sum_\nu K_{\lambda\nu} (K^{-1})_{\mu\nu}. \]Step 3: Recognize the matrix product. The expression \( \sum_\nu K_{\lambda\nu} (K^{-1})_{\mu\nu} = \sum_\nu K_{\lambda\nu} (K^{-T})_{\nu\mu} = (K K^{-T})_{\lambda\mu} \). Now, the key insight is that \( K^{-T} = (K^T)^{-1} \), and since \( K \) is upper unitriangular with respect to dominance order, \( K^T \) is lower unitriangular, and \( K K^{-T} = I \) (the identity matrix). This is because the transition matrix from \( s \) to \( m \) (which is \( K \)) and from \( m \) to \( h \) (which is \( K^T \), a consequence of the duality \( \langle h_\lambda, m_\mu \rangle = \delta_{\lambda\mu} \) and the expansion of \( h_\mu \) in the Schur basis being given by the transpose Kostka numbers) satisfy \( K \cdot K^T = \) (transition from \( s \) to \( h \), which is the identity up to reordering by unitriangularity). Therefore \( \langle s_\lambda, s_\mu \rangle = \delta_{\lambda\mu} \). \( \square \)
We verify this by expanding both sides to degree 2 (i.e., matching all terms \( \sum_\lambda s_\lambda(x) s_\lambda(y) \) for \( |\lambda| \leq 2 \)).
Left side — sum over partitions \( \lambda \) of weight 0, 1, and 2:
- \( |\lambda| = 0 \): \( s_\emptyset = 1 \). Contribution: \( 1 \cdot 1 = 1 \).
- \( |\lambda| = 1 \): \( s_{(1)} = x_1 + x_2 = e_1(x) \). Contribution: \( (x_1+x_2)(y_1+y_2) = e_1(x)e_1(y) \).
- \( |\lambda| = 2 \): two partitions. \( s_{(2)} = x_1^2 + x_1 x_2 + x_2^2 = h_2(x) \), and \( s_{(1,1)} = x_1 x_2 = e_2(x) \). Contribution: \( h_2(x) h_2(y) + e_2(x) e_2(y) \).
The degree-1 part is \( \sum_{i,j} x_i y_j = \bigl(\sum_i x_i\bigr)\bigl(\sum_j y_j\bigr) = e_1(x) e_1(y) \). ✓ matches the \( s_{(1)} \) term.
The degree-2 part is \( \sum_{i \leq i', j \leq j'} x_i x_{i'} y_j y_{j'} + \cdots \). More precisely, \( h_2(x) h_2(y) = \bigl(\sum_{i \leq i'} x_i x_{i'}\bigr)\bigl(\sum_{j \leq j'} y_j y_{j'}\bigr) \)… but this does not immediately equal the degree-2 part of the product. The correct computation uses the identity \( h_2(x) m_{(2)}(y) + h_{(1,1)}(x) m_{(1,1)}(y) = \) degree-2 part of \( \prod (1-x_i y_j)^{-1} \), which is precisely the Cauchy identity in the form \( \sum_\lambda h_\lambda(x) m_\lambda(y) \). For degree 2: \( h_2(x) m_{(2)}(y) + h_{(1,1)}(x) m_{(1,1)}(y) = h_2(x)(y_1^2+y_2^2) + h_1^2(x) \cdot y_1 y_2 \), and using \( s_{(2)} = h_2 - 0 \) and \( s_{(1,1)} = e_2 \) shows the \( h/m \) form matches the \( s/s \) form term by term via the Kostka matrix. \( \checkmark \)
The Kostka numbers satisfy \( s_\lambda = \sum_\mu K_{\lambda\mu} m_\mu \), so \( K_{\lambda\mu} = \langle s_\lambda, h_\mu \rangle \). The matrix \( K = (K_{\lambda\mu}) \) is upper unitriangular with respect to dominance order and has non-negative integer entries. The entries count SSYT, so positivity is obvious combinatorially; non-trivially, the dominance condition means \( K_{\lambda\mu} = 0 \) unless \( \lambda \geq_{\mathrm{dom}} \mu \).
| Bases \( f \), \( g \) | \( \langle f_\lambda, g_\mu \rangle \) |
|---|---|
| \( h_\lambda \), \( m_\mu \) | \( \delta_{\lambda\mu} \) |
| \( p_\lambda \), \( p_\mu \) | \( z_\lambda \delta_{\lambda\mu} \) |
| \( s_\lambda \), \( s_\mu \) | \( \delta_{\lambda\mu} \) |
| \( e_\lambda \), \( \ldots \) | (derived via \( \omega \)) |
Chapter 5: The RSK Correspondence
Why is RSK “deep”? Because a single bijection simultaneously explains at least four distinct phenomena that would otherwise seem unrelated:
The identity \( \sum_{\lambda \vdash n} (f^\lambda)^2 = n! \) — the number of pairs of SYT of the same shape equals \( n! \). This follows trivially from RSK (each permutation maps to a unique pair), but proving it without RSK requires a non-trivial representation-theoretic argument (Burnside’s formula applied to \( S_n \)).
The Cauchy identity \( \sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j}(1-x_iy_j)^{-1} \) — this generating function identity follows from RSK by summing over all non-negative integer matrices \( A \), identifying the weight of \( (A, P, Q) \) on both sides.
Longest increasing subsequences — the length of the longest increasing subsequence (LIS) of a permutation equals the first-row length of its RSK insertion tableau. This connection between a combinatorial optimization quantity and an algebraic invariant is non-obvious and was a deep observation of Schensted (1961).
Plactic monoid — the Knuth equivalence classes on words, defined by purely local moves, coincide exactly with the fibers of the RSK insertion map. This gives the free monoid a canonical quotient with rich structure and provides a combinatorial model for the polynomial representation ring of \( \mathrm{GL}(n) \).
The fact that one bijection unifies all four is the measure of RSK’s depth.
The Robinson-Schensted-Knuth (RSK) correspondence is one of the deepest bijections in combinatorics. In its most general form, RSK is a bijection between matrices \( A = (a_{ij})_{i,j \geq 1} \) of non-negative integers with finite sum \( N = \sum a_{ij} \), and pairs \( (P, Q) \) of SSYT of the same shape \( \lambda \vdash N \), where the content of \( P \) encodes column sums of \( A \) and the content of \( Q \) encodes row sums.
Row insertion. The key operation is inserting an integer \( k \) into a tableau \( T \). Find the leftmost entry in row 1 that exceeds \( k \); bump that entry to row 2, and insert \( k \) in its place. Repeat in row 2, and so on, until a new box is added at the end of some row. The result is a new SSYT \( T \leftarrow k \) of size one larger. Inserting entries one by one builds the insertion tableau \( P(A) \) while a recording tableau \( Q(A) \) tracks where each new box was added.
The final RSK output is the pair \( (P(231), Q(231)) \), both of shape \( \lambda = (2,1) \). This is consistent: \( f^{(2,1)} = 2 \), so there are \( (f^{(2,1)})^2 = 4 \) permutations in \( S_3 \) mapping to shape \( (2,1) \) under RSK, corresponding to the bulk of the \( 3! = 6 \) permutations (the remaining 2 permutations — the identity and the long permutation — map to shapes \( (3) \) and \( (1,1,1) \) respectively).
Key properties of RSK include: transposing \( A \) swaps \( P \) and \( Q \); the shape of \( P \) and \( Q \) are equal; and the Cauchy identity is the generating-function shadow, since summing over all \( A \) gives \( \sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j} (1-x_iy_j)^{-1} \).
- The inverse permutation satisfies \( w^{-1} \mapsto (Q(w), P(w)) \) — RSK of the inverse swaps the two tableaux.
- An involution \( w = w^{-1} \) maps to a pair with \( P = Q \).
- The length of the longest increasing subsequence of \( w \) equals \( \lambda_1 \), the first-row length of \( P(w) \) (Schensted's theorem, 1961).
The RSK output for \( w = 3142 \) is the pair of shape-\( (2,2) \) tableaux shown above. Both \( P \) and \( Q \) are SYT (entries increase along rows and down columns). We can verify: for \( n = 4 \), the partitions with their SYT counts are \( f^{(4)} = 1 \), \( f^{(3,1)} = 3 \), \( f^{(2,2)} = 2 \), \( f^{(2,1,1)} = 3 \), \( f^{(1,1,1,1)} = 1 \), and
\[ \sum_{\lambda \vdash 4} (f^\lambda)^2 = 1^2 + 3^2 + 2^2 + 3^2 + 1^2 = 1 + 9 + 4 + 9 + 1 = 24 = 4!\,. \checkmark \]The permutation \( w = 3142 \) maps to shape \( (2,2) \), contributing to the \( (f^{(2,2)})^2 = 4 \) permutations with RSK shape \( (2,2) \). One can verify that \( 1324, 2413, 3142, 4231 \) are exactly the 4 permutations in \( S_4 \) whose RSK shape is \( (2,2) \).
\( \mathrm{LIS}(w) \leq \lambda_1 \): We show that any increasing subsequence has length at most \( \lambda_1 \). Consider an increasing subsequence \( w_{i_1} < w_{i_2} < \cdots < w_{i_k} \) with \( i_1 < i_2 < \cdots < i_k \). As we insert \( w_{i_1}, w_{i_2}, \ldots, w_{i_k} \) into the tableau (during the RSK process), claim each \( w_{i_j} \) is placed in column at least \( j \). Proof: \( w_{i_1} \) is placed somewhere in row 1; \( w_{i_2} > w_{i_1} \) so when \( w_{i_2} \) is inserted into row 1, it bumps an element \( \geq w_{i_2} \) or is placed to the right of where \( w_{i_1} \) was placed — either way, it occupies a position at least as far right as \( w_{i_1} \), i.e., at least column 2. By induction, \( w_{i_j} \) is placed at column \( \geq j \). Since all boxes placed are in row 1 or later, the first row after all insertions has length \( \lambda_1 \geq k \).
\( \mathrm{LIS}(w) \geq \lambda_1 \): We exhibit an increasing subsequence of length \( \lambda_1 \). The first-row entries of \( P(w) = (e_1, e_2, \ldots, e_{\lambda_1}) \) form a strictly increasing sequence (by the row-insertion property). By a careful analysis of the RSK structure (tracking which entries of \( w \) eventually end up in row 1), one extracts an increasing subsequence of length \( \lambda_1 \) in \( w \). The key observation: the entry \( e_j \) in column \( j \) of row 1 was originally inserted (or bumped from another row) at a time after \( e_{j-1} \), by a value of \( w \) that was larger. \( \square \)
The Vershik-Kerov theorem (1977), independently proved by Logan and Shepp, states that for a uniformly random permutation \( w \in S_n \):
\[ \frac{\lambda_1(w)}{2\sqrt{n}} \xrightarrow{P} 1 \quad \text{as } n \to \infty. \]More precisely, \( \mathbb{E}[\lambda_1(w)] \sim 2\sqrt{n} \) and the fluctuations are on the scale \( n^{1/6} \). This is a law of large numbers for the LIS length. The deeper result (Baik-Deift-Johansson, 1999) identifies the fluctuation distribution as the Tracy-Widom GUE law — the same distribution that governs the largest eigenvalue of a \( n \times n \) random Gaussian Unitary Ensemble matrix as \( n \to \infty \). This universality, connecting a purely combinatorial quantity (LIS of a permutation) to random matrix theory through the RSK correspondence, is one of the deepest results in modern probability and combinatorics.
RSK for permutations. When \( A \) is a permutation matrix, \( P \) and \( Q \) are both SYT of the same shape \( \lambda \vdash n \). The bijection \( w \mapsto (P(w), Q(w)) \) immediately proves \( \sum_{\lambda \vdash n} (f^\lambda)^2 = n! \). The Knuth relations on words are local transformations that preserve the insertion tableau \( P \), and their equivalence classes form the plactic monoid. Dual RSK applies to 0-1 matrices and is the combinatorial shadow of the dual Cauchy identity.
Chapter 6: Representation Theory of the Symmetric Group
The connection between symmetric functions and representation theory is one of the most surprising and productive coincidences in mathematics. Frobenius (1900) discovered that the character table of \( S_n \) — a purely group-theoretic object — is exactly encoded by Schur functions. This reflects a deep structural fact: the ring of symmetric functions \( \Lambda \) and the representation ring of \( S_n \) are isomorphic as graded rings via the Frobenius characteristic map. The practical consequence is enormous: any identity among symmetric functions has an immediate representation-theoretic interpretation, and vice versa.
The irreducible complex representations of \( S_n \) are indexed by partitions \( \lambda \vdash n \). For each \( \lambda \), there is an irreducible representation \( V^\lambda \) (the Specht module) of dimension \( f^\lambda \). The decomposition \( \sum_{\lambda \vdash n} (f^\lambda)^2 = n! \) (proved by RSK) confirms that this list is complete: the number of irreducibles equals the number of conjugacy classes of \( S_n \) (= the number of partitions of \( n \)).
Reading off characters. Expanding in the power-sum basis:
\[ s_\lambda = \sum_{\mu \vdash n} \frac{\chi^\lambda(\mu)}{z_\mu} p_\mu, \]so \( \chi^\lambda(\mu) = z_\mu \langle s_\lambda, p_\mu \rangle \). The entire character table of \( S_n \) is encoded in the Schur functions. The Murnaghan-Nakayama rule computes each \( \chi^\lambda(\mu) \) as a signed sum of border-strip fillings.
Trivial representation \( \lambda = (3) \): Any border-strip filling of shape \( (3) \) with strips of sizes given by \( \mu \) has height 0 at each step (all strips are horizontal in a single row). So \( \chi^{(3)}(\mu) = 1 \) for all \( \mu \vdash 3 \).
Sign representation \( \lambda = (1^3) \): All border strips must be vertical columns (a single column has height = length \( - 1 \)). For \( \mu = (3) \): one strip of size 3, height 2, sign \( (-1)^2 = 1 \). For \( \mu = (2,1) \): strip of size 2 (height 1, sign \(-1\)) then size 1 (height 0, sign \(+1\)), product \(-1\). For \( \mu = (1^3) \): three strips of size 1, each height 0, product \(+1\).
Standard representation \( \lambda = (2,1) \): For \( \mu = (1^3) \): filling with three size-1 strips gives each new box as a corner; the count is \( f^{(2,1)} = 2 \). For \( \mu = (3) \): one border strip of size 3 filling all of \( (2,1) \); the strip \( (2,1)/\emptyset \) occupies 2 rows, \( \mathrm{ht}=1 \), so \( \chi^{(2,1)}(3) = -1 \). For \( \mu = (2,1) \): by orthogonality of characters, \( \chi^{(2,1)}(2,1) = 0 \).
The character table of \( S_3 \) is:
\[ \begin{array}{c|ccc} & (3) & (2,1) & (1^3) \\\hline V^{(3)} & 1 & 1 & 1 \\ V^{(2,1)} & 2 & 0 & -1 \\ V^{(1^3)} & 1 & -1 & 1 \end{array} \]We compute select character values using the Murnaghan-Nakayama rule. Recall \( \chi^\lambda(\mu) \) is the signed count of border-strip tableaux of shape \( \lambda \) and type \( \mu \) (we add border strips of sizes \( \mu_1, \mu_2, \ldots \) in sequence).
Row \( \lambda = (2,1,1) \):
- \( \mu = (1^4) \): each strip has size 1 (corner boxes), no signing. This counts SYT of shape \( (2,1,1) \), so \( \chi^{(2,1,1)}(1^4) = f^{(2,1,1)} = 3 \).
- \( \mu = (4) \): add one border strip of size 4 filling all of \( (2,1,1) \). The shape \( (2,1,1)/\emptyset = (2,1,1) \) is a valid border strip (connected, no \( 2\times 2 \) block — indeed it is an "L"-shape). It occupies rows 1, 2, 3, so height \( = 3-1 = 2 \), sign \( (-1)^2 = +1 \). So \( \chi^{(2,1,1)}((4)) = 1 \).
- \( \mu = (2,2) \): add a strip of size 2 to \( \emptyset \) to get some shape \( \rho \), then add another strip of size 2 from \( \rho \) to reach \( (2,1,1) \). First strip options filling exactly \( \rho \subseteq (2,1,1) \) with \( |\rho|=2 \): the shape \( (2) \) — horizontal strip of height 0, sign \( +1 \); or \( (1,1) \) — vertical strip of height 1, sign \( -1 \). Then from \( (2) \), add size-2 strip to reach \( (2,1,1) \): skew \( (2,1,1)/(2) \) has boxes \( (2,1),(3,1) \), a vertical strip of height 1, sign \( -1 \). Total for this branch: \( (+1)\cdot(-1) = -1 \). From \( (1,1) \), add size-2 strip to reach \( (2,1,1) \): skew \( (2,1,1)/(1,1) \) has boxes \( (1,2),(3,1) \) — these are not connected (no shared edge), so not a valid border strip. ✗. Therefore \( \chi^{(2,1,1)}((2,2)) = -1 \).
- \( \mu = (3,1) \): add strip of size 3 to \( \emptyset \), then strip of size 1. First strip: \( (2,1,1)/\emptyset \) restricted to a size-3 subshape. Options: shape \( (3) \) (horizontal, height 0, sign \(+1\)); shape \( (2,1) \) (height 1, sign \(-1\)); shape \( (1,1,1) \) (height 2, sign \(+1\)). Then from each, add a corner box to reach \( (2,1,1) \): (a) from \( (3) \): skew \( (2,1,1)/(3) \) — but \( (3) \not\subseteq (2,1,1) \) since \( \lambda_1 = 2 < 3 \). Invalid. (b) from \( (2,1) \): remaining boxes \( (3,1) \), a single box, height 0, sign \(+1\). Total: \( (-1)(+1) = -1 \). (c) from \( (1,1,1) \): but \( (1,1,1) \not\subseteq (2,1,1) \)? \( (1,1,1)_3 = 1 \leq (2,1,1)_3 = 1 \) ✓, and \( (1,1,1)_1 = 1 \leq 2, (1,1,1)_2 = 1 \leq 1 \) ✓. Remaining box: \( (1,2) \), single box, sign \(+1\). Total: \( (+1)(+1) = +1 \). So \( \chi^{(2,1,1)}(3,1) = -1 + 1 = 0 \).
- \( \mu = (2,1^2) \): by orthogonality of characters, \( \sum_{\mu} |\mathrm{class}(\mu)| \chi^\lambda(\mu)^2 = |S_4| \cdot [\lambda = \lambda] \). Using values above: \( 1\cdot9 + 6\cdot\chi^2 + 3\cdot1 + 8\cdot0 + 6\cdot1 = 24 \), giving \( 6\chi^2 = 24-9-3-6 = 6 \), so \( \chi = \pm 1 \). The value is \( \chi^{(2,1,1)}(2,1^2) = -1 \) (consistent with the sign representation twist).
The full character table of \( S_4 \):
\[ \begin{array}{c|ccccc} \lambda \backslash \mu & (1^4) & (2,1^2) & (2^2) & (3,1) & (4) \\\hline (4) & 1 & 1 & 1 & 1 & 1 \\ (3,1) & 3 & 1 & -1 & 0 & -1 \\ (2,2) & 2 & 0 & 2 & -1 & 0 \\ (2,1,1) & 3 & -1 & -1 & 0 & 1 \\ (1^4) & 1 & -1 & 1 & 1 & -1 \end{array} \]One can verify orthogonality: rows are orthogonal with respect to the inner product weighted by class sizes, and the sum of squared dimensions gives \( 1+9+4+9+1 = 24 = |S_4| \) ✓.
where \( W^\lambda \) is the irreducible polynomial \( \mathrm{GL}(V) \)-representation of highest weight \( \lambda \) (the Schur module, or Weyl module), and \( V^\lambda \) is the Specht module (irreducible \( S_n \)-representation) indexed by \( \lambda \). The condition \( \ell(\lambda) \leq d \) means only partitions with at most \( d \) parts appear (since \( V = \mathbb{C}^d \) has only \( d \) coordinates).
The consequence is remarkable: the study of polynomial representations of \( \mathrm{GL}(d) \) and the study of representations of \( S_n \) are two sides of the same coin. Knowing one family of irreps and how they pair in \( V^{\otimes n} \) completely determines the other. The Frobenius characteristic map is the algebraic encoding of this duality: \( \mathrm{ch}(V^\lambda) = s_\lambda \) in \( \Lambda \), while the character of \( W^\lambda \) evaluated at eigenvalues \( x_1,\ldots,x_d \) is also \( s_\lambda(x_1,\ldots,x_d) \). The RSK correspondence provides the combinatorial shadow: an RSK-style bijection on \( V^{\otimes n} \) (via Weyl’s construction using Young symmetrizers) makes the decomposition above explicit.
summed over \( \lambda \vdash n \) obtained from \( \mu \) by adding a single box.
The branching rule has a simple combinatorial proof: the standard Young tableaux of shape \( \lambda \) containing \( n \) in a corner box (so that removing \( n \) gives a SYT of shape \( \mu \)) correspond precisely to the \( V^\mu \) summands in the restriction. Since each SYT of shape \( \lambda \) contains \( n \) in exactly one corner box, the SYT of shape \( \lambda \) partition into groups indexed by which corner holds \( n \), and each group has size \( f^\mu \) where \( \mu \) is the shape after removing that corner. The branching rule underlies the recursive computation of \( f^\lambda \) as a sum over “inner corners” of \( f^\mu \), providing an alternative to the hook-length formula.
Induction and restriction. Under the Frobenius map, induced representations correspond to products of symmetric functions. If \( \mu \vdash k \) and \( \nu \vdash m \) with \( k + m = n \), then
\[ \mathrm{ch}\!\left(\mathrm{Ind}_{S_k \times S_m}^{S_n} V^\mu \otimes V^\nu\right) = s_\mu \cdot s_\nu = \sum_\lambda c^\lambda_{\mu\nu} s_\lambda, \]and \( c^\lambda_{\mu\nu} \) counts the multiplicity of \( V^\lambda \) in the induced representation. Schur-Weyl duality connects \( S_n \) and \( \mathrm{GL}(V) \): both act on \( V^{\otimes n} \) and centralize each other, giving the decomposition \( V^{\otimes n} \cong \bigoplus_{\lambda} W^\lambda \otimes V^\lambda \) that simultaneously exhibits both families of irreps.
Chapter 7: Littlewood-Richardson Rule and Applications
The Littlewood-Richardson (LR) coefficients \( c^\lambda_{\mu\nu} \) are defined by the product formula
\[ s_\mu \cdot s_\nu = \sum_\lambda c^\lambda_{\mu\nu} s_\lambda. \]They also equal the multiplicity of \( V^\lambda \) in \( \mathrm{Ind}_{S_{|\mu|} \times S_{|\nu|}}^{S_n} V^\mu \otimes V^\nu \), and appear in the decomposition of tensor products of \( \mathrm{GL}(n) \)-representations. Their non-negativity is obvious from representation theory but non-trivial combinatorially; the LR rule provides an explicit count.
The LR rule. A word \( w = w_1 w_2 \cdots w_k \) is a ballot sequence (or lattice word) if every initial segment \( w_1 \cdots w_j \) contains at least as many \( i \)’s as \( (i+1) \)’s for all \( i \geq 1 \). Given a skew SSYT \( T \) of shape \( \lambda/\mu \), its reverse reading word \( \mathrm{rw}(T) \) is obtained by reading each row right-to-left, starting from the top row.
The candidates are \( \lambda \in \{(4,1), (3,2), (3,1,1), (2,2,1)\} \).
\( \lambda = (4,1) \): Skew \( (4,1)/(2,1) \) has boxes \( (1,3),(1,4) \). Fill with one 1 and one 2: the only SSYT filling with weakly increasing rows is \( 1,2 \). Reverse reading word: row 1 read right-to-left gives \( 2, 1 \). First character is 2: not ballot (need \(\#1 \geq \#2\)). ✗ So \( c^{(4,1)}_{(2,1),(1,1)} = 0 \).
\( \lambda = (3,2) \): Skew \( (3,2)/(2,1) \) has boxes \( (1,3) \) and \( (2,2) \). Content \( (1,1) \): place one 1 and one 2. Two fillings: \( \{(1,3)=1,(2,2)=2\} \) gives reading word \( 1, 2 \) (row 1: \( 1 \), row 2: \( 2 \)). Ballot? ✓. The filling \( \{(1,3)=2,(2,2)=1\} \) gives word \( 2, 1 \). Not ballot. ✗. So \( c^{(3,2)}_{(2,1),(1,1)} = 1 \).
\( \lambda = (3,1,1) \): Skew has boxes \( (1,3) \) and \( (3,1) \). Filling with \( 1 \) at \( (1,3) \), \( 2 \) at \( (3,1) \): reading word \( 1, 2 \). Ballot ✓. Filling \( 2 \) at \( (1,3) \), \( 1 \) at \( (3,1) \): word \( 2, 1 \). ✗. So \( c^{(3,1,1)}_{(2,1),(1,1)} = 1 \).
\( \lambda = (2,2,1) \): Skew has boxes \( (2,2) \) and \( (3,1) \). Filling \( 1 \) at \( (2,2) \), \( 2 \) at \( (3,1) \): word \( 1, 2 \). Ballot ✓. Other filling: word \( 2,1 \). ✗. So \( c^{(2,2,1)}_{(2,1),(1,1)} = 1 \).
Conclusion:
\[ s_{(2,1)} \cdot s_{(1,1)} = s_{(3,2)} + s_{(3,1,1)} + s_{(2,2,1)}. \]Content \( (2) \) means exactly two boxes, both filled with 1. The reverse reading word of any such tableau is \( 1,1 \). A word \( 1,1 \) is automatically a ballot sequence (at every prefix, count of 1’s is at least count of 2’s, 3’s, etc., and with no 2’s that condition is trivially satisfied). So the only constraint is that the filling is a valid skew SSYT of shape \( \lambda/(3,1) \): weakly increasing rows, strictly increasing columns — but with all entries equal to 1, the column-strictness is automatically satisfied only if no two boxes of the skew shape are in the same column.
Thus the condition reduces to: \( \lambda/(3,1) \) is a horizontal strip (at most one new box per column). This is exactly the Pieri rule condition! So we recover the Pieri rule for \( s_{(3,1)} \cdot h_2 \) from the LR rule, as expected when \( \nu = (2) \) (a single-row partition).
From our earlier Pieri computation: the valid shapes are \( (5,1), (4,2), (4,1,1), (3,3), (3,2,1) \), each with LR coefficient 1. Therefore:
\[ s_{(3,1)} \cdot s_{(2)} = s_{(5,1)} + s_{(4,2)} + s_{(4,1,1)} + s_{(3,3)} + s_{(3,2,1)}. \]This confirms that the LR rule specializes correctly to the Pieri rule when \( \nu \) is a one-row partition.
First, identify the skew shape \( (4,2,1)/(3,1) \): from \( \lambda = (4,2,1) \) remove the boxes of \( \mu = (3,1) \). Row 1: \( \lambda_1 = 4, \mu_1 = 3 \), so one new box in row 1 (at column 4). Row 2: \( \lambda_2 = 2, \mu_2 = 1 \), so one new box (at column 2). Row 3: \( \lambda_3 = 1, \mu_3 = 0 \), so one new box (at column 1). The skew shape has three boxes: \( (1,4), (2,2), (3,1) \).
Content \( (2,1) \): place two 1’s and one 2 in these three boxes. Valid skew SSYT fillings (weakly increasing rows, strictly increasing columns — noting the boxes are isolated in their respective rows, so the row condition is trivially satisfied):
- Filling A: \( (1,4) = 1,\ (2,2) = 1,\ (3,1) = 2 \). Column check: column 4 has only box \( (1,4) \) in the skew; column 2 has only \( (2,2) \); column 1 has only \( (3,1) \). No column has two filled boxes, so column-strictness is vacuous. Reverse reading word: row 3 right-to-left: 2; row 2 right-to-left: 1; row 1 right-to-left: 1. Word: \( 2, 1, 1 \). Ballot check: first character is 2, but we need count of 1's \( \geq \) count of 2's at every prefix. Prefix \( 2 \): one 2, zero 1's. Not ballot. ✗
- Filling B: \( (1,4) = 1,\ (2,2) = 2,\ (3,1) = 1 \). Check column: columns 4, 2, 1 each have one box; no column strictness issue. But check row 2: the single box \( (2,2) = 2 \) — fine. Reverse reading word: row 3: 1; row 2: 2; row 1: 1. Word: \( 1, 2, 1 \). Ballot check: prefix \( 1 \): one 1, zero 2's ✓; prefix \( 1,2 \): one 1, one 2 — equal, so one 1 \( \geq \) one 2 is borderline (need \( \#1 \geq \#2 \), and \( 1 \geq 1 \) ✓); prefix \( 1,2,1 \): two 1's, one 2 ✓. Ballot! ✓
- Filling C: \( (1,4) = 2,\ (2,2) = 1,\ (3,1) = 1 \). Column: OK (no repeated columns). Reverse reading word: row 3: 1; row 2: 1; row 1: 2. Word: \( 1, 1, 2 \). Ballot check: \( 1 \geq 0 \) ✓; \( 2 \geq 0 \) ✓; \( 2 \geq 1 \) ✓. Ballot! ✓
So there are exactly 2 valid ballot SSYT, giving \( c^{(4,2,1)}_{(3,1),(2,1)} = 2 \).
Jeu de taquin (Schützenberger 1977, Thomas 1974): Rectification of skew tableaux by sliding operations. The number of skew SSYT of shape \( \lambda/\mu \) and content \( \nu \) that rectify to the canonical tableau of shape \( \mu \) equals \( c^\lambda_{\mu\nu} \). This proof is elementary but requires verifying that rectification is well-defined (independent of slide order) and compatible with the ballot condition.
RSK on biwords: The Cauchy identity \( s_\mu \cdot s_\nu = \sum_\lambda c^\lambda_{\mu\nu} s_\lambda \) can be proved by applying RSK to matrices corresponding to pairs of tableaux of shapes \( \mu \) and \( \nu \), producing pairs of tableaux of shape \( \lambda \). The ballot condition arises from the definition of RSK applied to biwords.
Hive model (Knutson-Tao 1999): A hive is a triangular array of non-negative integers satisfying certain “rhombus inequalities.” The number of integer hives with boundary data \( (\mu, \nu, \lambda) \) equals \( c^\lambda_{\mu\nu} \). This model proved the Saturation theorem and Horn conjecture.
Puzzles (Knutson-Tao-Woodward 2004): A puzzle is a tiling of a triangular region by three types of puzzle pieces (labelled by 0, 1, and a “rhombus”). The number of puzzles with boundary labels \( (\mu,\nu,\lambda) \) equals \( c^\lambda_{\mu\nu} \). This is used in quantum cohomology calculations.
Crystal bases (Kashiwara): Using the theory of quantum groups at \( q=0 \), one constructs crystal graphs on SSYT. The LR coefficient counts paths in a tensor product of crystals, and the ballot condition corresponds to the highest-weight condition in the crystal.
Geometric Satake (Mirkovic-Vilonen): Via the geometric Satake correspondence, LR coefficients count dimensions of intersections of Schubert varieties in the affine Grassmannian, connecting the LR rule to the Langlands program and geometric representation theory.
Each proof generalizes differently: the hive and puzzle proofs extend to K-theory (equivariant LR); crystal bases extend to Kac-Moody algebras; geometric Satake extends to other reductive groups.
Jeu de taquin (Schützenberger’s sliding algorithm) provides an alternative approach. A forward slide at an inner corner of a skew shape moves a box left or up; an evacuation sequence of slides rectifies the skew tableau to a straight shape. The remarkable fact is that rectification is independent of the order of slides. The LR rule can be restated: \( c^\lambda_{\mu\nu} \) counts SSYT of shape \( \nu \) that rectify to the canonical tableau of shape \( \mu \).
Special cases. When \( \nu = (n) \), \( s_\nu = h_n \) and the LR rule reduces to the Pieri rule (each \( c^\lambda_{\mu,(n)} \in \{0,1\} \)). When \( \nu = (1^n) \), \( s_\nu = e_n \) and we get the other Pieri rule.
Chapter 8: Further Topics — Quasisymmetric Functions and Applications
Quasisymmetric functions \( \mathrm{QSym} \) generalize symmetric functions by relaxing the symmetry condition. A formal power series \( f \in \mathbb{Z}[[x_1, x_2, \ldots]] \) is quasisymmetric if for every composition \( \alpha = (\alpha_1, \ldots, \alpha_k) \), the coefficient of \( x_{i_1}^{\alpha_1} \cdots x_{i_k}^{\alpha_k} \) depends only on \( \alpha \), not on the choice of indices \( i_1 < \cdots < i_k \). The inclusion \( \Lambda \subset \mathrm{QSym} \) holds, with \( m_\lambda = \sum_\alpha M_\alpha \) (sum over compositions \( \alpha \) that are rearrangements of \( \lambda \)).
where \( \beta \) refines \( \alpha \) means \( \alpha \) is obtained from \( \beta \) by summing consecutive parts. Both \( \{M_\alpha\} \) and \( \{F_\alpha\} \) (indexed by compositions of \( n \)) are \( \mathbb{Z} \)-bases of \( \mathrm{QSym}^n \). The Schur function expands as \( s_\lambda = \sum_\alpha F_\alpha \), summed over compositions \( \alpha \) arising as descent compositions of standard Young tableaux of shape \( \lambda \).
Compare with \( M_{(2,1)} = x_1^2 x_2 + x_1^2 x_3 + x_2^2 x_3 \): same monomials but with larger exponent first.
\[ F_{(1,2)} = M_{(1,2)} + M_{(1,1,1)} = (x_1 x_2^2 + x_1 x_3^2 + x_2 x_3^2) + x_1 x_2 x_3. \]The extra term \( x_1 x_2 x_3 \) in \( F_{(1,2)} \) (but not \( M_{(1,2)} \)) reflects the coarsening: a monomial of type \( (1,1,1) \) has a “subsequence” of type \( (1,2) \) (the first variable gets exponent 1, and the remaining two together contribute exponent \( 1+1 = 2 \)).
Stanley’s theory of \( P \)-partitions. Given a labeled poset \( P \) on \( [n] \), a \( P \)-partition is an order-reversing map \( f : P \to \mathbb{Z}_{>0} \). The generating function \( \Gamma(P) = \sum_f x_{f(1)} \cdots x_{f(n)} \) is always quasisymmetric. If \( P \) is a forest (or more generally an “incomparability graph” of a forest), then \( \Gamma(P) \) is symmetric. The fundamental quasisymmetric functions arise as \( \Gamma \) applied to chains with a specific labeling.
Noncommutative symmetric functions \( \mathrm{NSym} \) form the dual Hopf algebra to \( \mathrm{QSym} \). \( \mathrm{NSym} \) is freely generated as an algebra by noncommutative analogs \( H_n \) of the \( h_n \), and has bases of ribbon Schur functions \( r_\alpha \) indexed by compositions. The dual pairing \( \langle r_\alpha, F_\beta \rangle = \delta_{\alpha\beta} \) mirrors the \( \langle s_\lambda, s_\mu \rangle = \delta_{\lambda\mu} \) duality. The descent algebra of \( S_n \) embeds into \( \mathrm{NSym} \), connecting these algebraic structures to the combinatorics of permutation descents.
The chromatic symmetric function is:
\[ X_{P_3} = \sum_{\substack{a,b,c \geq 1 \\ a \neq b,\ b \neq c}} x_a x_b x_c. \]To express this in terms of the standard symmetric function bases, observe:
\[ X_{P_3} = \sum_{a,b,c \geq 1} x_a x_b x_c - \sum_{\substack{a,b,c \geq 1 \\ a=b}} x_a x_b x_c - \sum_{\substack{a,b,c \geq 1 \\ b=c}} x_a x_b x_c + \sum_{\substack{a,b,c \geq 1 \\ a=b=c}} x_a x_b x_c \]by inclusion-exclusion on the bad events \( a=b \) and \( b=c \). In terms of symmetric functions:
\[ X_{P_3} = h_1^3 - h_2 h_1 - h_1 h_2 + h_3 = h_1^3 - 2 h_1 h_2 + h_3. \]To expand in the \( e \)-basis, use the Newton identities and the transition matrix. Alternatively, note the direct identity: applying \( \omega \) to \( h_1^3 - 2h_1 h_2 + h_3 \) gives \( e_1^3 - 2 e_1 e_2 + e_3 \), but since \( X_{P_3} \) must be expressed in the \( e \)-basis from scratch, let us use the expansion:
\[ h_1 = e_1, \quad h_1^3 = e_1^3, \quad h_2 = e_1^2 - e_2, \quad h_3 = e_1^3 - 2e_1 e_2 + e_3. \]Substituting:
\[ X_{P_3} = e_1^3 - 2e_1(e_1^2 - e_2) + (e_1^3 - 2e_1 e_2 + e_3) = e_1^3 - 2e_1^3 + 2e_1 e_2 + e_1^3 - 2e_1 e_2 + e_3 = e_3. \]Wait — let us redo this more carefully. We have \( h_1 h_2 = e_1(e_1^2 - e_2) = e_1^3 - e_1 e_2 \). So:
\[ X_{P_3} = e_1^3 - 2(e_1^3 - e_1 e_2) + (e_1^3 - 2e_1 e_2 + e_3) = e_1^3 - 2e_1^3 + 2e_1 e_2 + e_1^3 - 2e_1 e_2 + e_3 = e_3 + 2e_{(2,1)} - 2e_{(2,1)}\ldots \]Let us be systematic. In terms of \( e \)-expansion of the \( h \)-monomials appearing (in \( n \) variables):
\[ h_1^3 = (x_1+x_2+\cdots)^3 = m_{(3)} + 3m_{(2,1)} + 6m_{(1,1,1)}, \]\[ h_1 h_2 = m_{(3)} + 2m_{(2,1)} + 3m_{(1,1,1)},\quad h_3 = m_{(3)} + m_{(2,1)} + m_{(1,1,1)}. \]Therefore:
\[ X_{P_3} = (m_{(3)}+3m_{(2,1)}+6m_{(1,1,1)}) - 2(m_{(3)}+2m_{(2,1)}+3m_{(1,1,1)}) + (m_{(3)}+m_{(2,1)}+m_{(1,1,1)}) = 0 \cdot m_{(3)} + 0 \cdot m_{(2,1)} + 1 \cdot m_{(1,1,1)}. \]So \( X_{P_3} = m_{(1,1,1)} = e_3 \) (in 3 or more variables). Let us verify the chromatic polynomial: specializing \( x_i = 1 \) for \( i \leq n \) and \( x_i = 0 \) for \( i > n \) gives \( X_{P_3}(1^n) = e_3(1^n) = \binom{n}{3} \)… but that is not right for the chromatic polynomial of \( P_3 \). The chromatic polynomial is \( \chi_{P_3}(n) = n(n-1)^2 \): choose color for vertex 2 (\( n \) ways), then vertex 1 must differ from vertex 2 (\( n-1 \) ways), and vertex 3 must differ from vertex 2 (\( n-1 \) ways). So \( \chi_{P_3}(n) = n(n-1)^2 \), which for \( n=3 \) gives \( 3 \cdot 4 = 12 \).
The resolution: \( m_{(1,1,1)} \) specialized to \( 1^n \) is the number of strictly increasing monomials \( x_a x_b x_c \) with \( a < b < c \leq n \), which is \( \binom{n}{3} \). But the chromatic polynomial counts ordered colorings \( (a,b,c) \) with \( a \neq b, b \neq c \) (not requiring all distinct). The generating function \( X_{P_3} \) sums \( x_a x_b x_c \) with \( a \neq b, b \neq c \) — this is symmetric but the monomial \( x_a x_b x_c \) with \( a = c \neq b \) contributes (e.g., \( x_1^2 x_2 \)). So \( X_{P_3} = m_{(2,1)} + m_{(1,1,1)} \) actually:
\[ X_{P_3} = \sum_{\substack{a \neq b,\, b \neq c}} x_a x_b x_c = m_{(2,1)} + 2m_{(1,1,1)}\ldots \]More precisely, the monomials are: (i) \( a = c \neq b \): contributes \( x_a^2 x_b \) terms, giving \( m_{(2,1)} \); (ii) \( a,b,c \) all distinct: contributes \( x_a x_b x_c \) terms, giving \( 2 m_{(1,1,1)} \) (factor 2 since for each set \( \{a,b,c\} \) there are 2 valid ordered triples with \( a \neq b, b \neq c, a \neq c \)). So \( X_{P_3} = m_{(2,1)} + 2m_{(1,1,1)} \). Specializing: \( X_{P_3}(1^n) = |\{(a,b): a,b \leq n, a \neq b\}| \cdot (n) = \ldots \) Actually \( m_{(2,1)}(1^n) = n(n-1) \) (choose which index gets squared, then which other index appears) and \( m_{(1,1,1)}(1^n) = \binom{n}{3} \cdot 6/6 = \binom{n}{3}\cdot 1\)… let us just verify directly: \( X_{P_3}(1^n) = m_{(2,1)}(1^n) + 2m_{(1,1,1)}(1^n) = n(n-1) + 2\binom{n}{3} = n(n-1) + n(n-1)(n-2)/3\). For \( n=3 \): \( 6 + 2 = 8 \neq 12 \). Something is off.
Let me recount directly: the valid colorings \( (a,b,c) \in \{1,\ldots,n\}^3 \) with \( a \neq b, b \neq c \) number \( n(n-1)^2 \). The generating function \( X_{P_3} = \sum x_a x_b x_c \) over these is a genuine symmetric function, and \( X_{P_3}(1^n) \) counts those colorings, so \( X_{P_3}(1^n) = n(n-1)^2 \). In the monomial expansion: terms of the form \( x_i^2 x_j \) arise when \( a = c = i \neq b = j \) or \( a = i \neq b = j = c \) (but wait \( b = c = j \) and \( a = i \neq b \), requiring \( b \neq c \) which fails). So \( b=c \) is excluded. Thus terms \( x_i^2 x_j \) arise only from \( a=c=i, b=j \), giving \( n(n-1) \) pairs \( (i,j) \), but in the monomial \( x_i^2 x_j \) the pair \( (i,j) \) and \( (j,i) \) are the same monomial up to relabeling… Actually \( m_{(2,1)} \) in \( n \) variables has \( n(n-1) \) monomials (choose the index for the exponent 2 and the index for exponent 1). Each \( x_i^2 x_j \) arises from exactly one colored vertex sequence \( (i,j,i) \). So the coefficient of \( m_{(2,1)} \) in \( X_{P_3} \) is 1. Terms of the form \( x_i x_j x_k \) (\( i,j,k \) distinct) arise from colorings where \( a,b,c \) are a permutation of \( \{i,j,k\} \) with \( a \neq b, b \neq c \). From the 6 permutations of \( \{i,j,k\} \), those satisfying \( a \neq b \) and \( b \neq c \): all 6 satisfy \( a \neq b \) (all distinct), but we need \( b \neq c \), which fails for \( (i,j,j),(j,i,i),(k,j,j),\ldots \) — but wait, since all of \( a,b,c \) are from \( \{i,j,k\} \) pairwise distinct, all 6 permutations have \( a \neq b \) and \( b \neq c \) automatically. So all 6 permutations of \( (i,j,k) \) are valid, and each contributes \( x_i x_j x_k \). Since \( m_{(1,1,1)} = \sum_{i Therefore \( X_{P_3} = m_{(2,1)} + 6 m_{(1,1,1)} \), and \( X_{P_3}(1^n) = n(n-1) + 6\binom{n}{3} = n(n-1) + n(n-1)(n-2) = n(n-1)(1 + n-2) = n(n-1)^2 \) ✓. This matches the chromatic polynomial of \( P_3 \). The \( e \)-basis expansion: using \( m_{(2,1)} = e_{(2,1)} - 3e_3 \) (from the Kostka matrix for \( n=3 \) inverted) and \( m_{(1,1,1)} = e_3 \) (in 3 variables): All coefficients of \( X_{P_3} \) in the \( e \)-basis are positive, consistent with the Stanley-Stembridge conjecture (paths are incomparability graphs of unit interval orders).
- Schur functions: \( P_\lambda(x;t,t) = s_\lambda(x) \) (the \( q=t \) specialization).
- Hall-Littlewood polynomials: \( P_\lambda(x;0,t) = P_\lambda(x;t) \), the Hall-Littlewood polynomials appearing in the theory of finite fields and \( p \)-adic groups.
- Jack polynomials: Taking \( q = t^\alpha \) and \( t \to 1 \) gives the Jack polynomials \( P_\lambda(x;\alpha) \), a one-parameter deformation of Schur functions connected to the Calogero-Sutherland model in mathematical physics.
- Zonal polynomials: \( P_\lambda(x;0,0) \) gives zonal polynomials appearing in multivariate statistics and the theory of symmetric spaces.
The modified Macdonald polynomials \( \tilde{H}_\lambda(x;q,t) \) are defined so that \( \tilde{H}_\lambda = \sum_\mu \tilde{K}_{\lambda\mu}(q,t) s_\mu \), where \( \tilde{K}_{\lambda\mu}(q,t) \in \mathbb{Z}_{\geq 0}[q,t] \) are the \( (q,t) \)-Kostka polynomials (Macdonald’s positivity conjecture, proved by Haiman 2001). The specialization \( \tilde{K}_{\lambda\mu}(1,1) = K_{\lambda\mu} \) recovers the ordinary Kostka numbers. The polynomials \( \tilde{K}_{\lambda\mu}(0,t) \) are the Kostka-Foulkes polynomials, which were known before Macdonald’s work to be polynomials in \( t \) with non-negative integer coefficients (Lascoux-Schützenberger 1978), arising as Kazhdan-Lusztig polynomials for type A and encoding the \( t \)-analog of Kostka numbers via cocharge statistics on SSYT.
The diagonal harmonics ring \( \mathrm{DH}_n = \mathbb{C}[x_1,\ldots,x_n,y_1,\ldots,y_n]/I^+ \) (where \( I^+ \) is the ideal generated by all positive-degree \( S_n \)-invariants acting diagonally) has dimension \( (n+1)^{n-1} \) — this is the “\( (n+1)^{n-1} \) theorem” (Haiman), connecting to the number of parking functions. The doubly-graded Hilbert series of \( \mathrm{DH}_n \) as an \( S_n \)-representation is given by the sum \( \sum_\lambda \tilde{H}_\lambda(x;q,t) \), relating diagonal harmonics directly to Macdonald polynomials. The geometry underlying all of this is the Hilbert scheme \( \mathrm{Hilb}^n(\mathbb{C}^2) \) of \( n \) points in the plane.
Chromatic symmetric functions. For a graph \( G = (V, E) \), Stanley defined
\[ X_G = \sum_{\kappa : V \to \mathbb{Z}_{>0},\ \kappa \text{ proper}} \prod_{v \in V} x_{\kappa(v)}, \]a symmetric function generalizing the chromatic polynomial \( \chi_G(n) = X_G(1^n) \). Expanding \( X_G = \sum_\lambda c_\lambda e_\lambda \) in the \( e \)-basis, the coefficients \( c_\lambda \) count proper colorings of type \( \lambda \).
Macdonald polynomials. The Macdonald symmetric functions \( \tilde{H}_\lambda(x; q, t) \) are a two-parameter family that specialize at various limits: at \( q = t \) they yield Schur functions; at \( q = 0 \) they give Hall-Littlewood polynomials; and at \( t = q^\alpha, q \to 1 \) they give Jack polynomials. The \( (q,t) \)-Kostka polynomials \( \tilde{K}_{\lambda\mu}(q,t) \) are defined by \( \tilde{H}_\lambda = \sum_\mu \tilde{K}_{\lambda\mu} s_\mu \). Macdonald conjectured \( \tilde{K}_{\lambda\mu}(q,t) \in \mathbb{Z}_{\geq 0}[q,t] \); this Macdonald positivity conjecture was proved by Haiman (2001).
Schubert calculus and enumerative geometry. The connection between Schur functions and geometry goes further: Schubert polynomials \( \mathfrak{S}_w \) (Lascoux-Schützenberger) represent cohomology classes of Schubert varieties in the complete flag variety, and specialize to Schur polynomials when \( w \) is a Grassmannian permutation. The quantum cohomology ring \( QH^*(\mathrm{Gr}(k,n)) \) has a quantum LR rule where the structure constants count rational curves meeting three Schubert varieties. These geometric applications demonstrate that symmetric function theory is not merely combinatorial abstraction: it encodes the enumerative geometry of some of the most studied spaces in mathematics.
Chapter 9: Jeu de Taquin and Rectification
Jeu de taquin (“the teasing game”) is Schützenberger’s elegant sliding algorithm on skew Young tableaux. The name reflects the puzzle-like nature of the operation: one repeatedly slides entries into an empty cell, as in the 15-puzzle. Beyond its intrinsic elegance, jeu de taquin is one of the key tools in algebraic combinatorics — it provides an alternative proof of the Littlewood-Richardson rule, defines canonical bijections on tableaux, and underlies both the promotion and evacuation operators on standard Young tableaux that generate a mysterious cyclic action called the toggle group.
The fundamental result — that the final rectified shape is independent of the order in which slides are applied — is non-trivial and was proved by Schützenberger in 1977. It means rectification is a well-defined map from skew tableaux to straight tableaux, depending only on the entries and not on any choices.
A backward slide into an outer corner of \( \lambda \) runs the same procedure in reverse: at each step, slide the larger of the entry above and the entry to the left into the empty cell. The rectification of a skew tableau \( T \) is the result of performing forward slides until no inner corners remain, producing a straight-shape tableau.
The skew shape \( (3,3)/(2,1) \) has boxes at positions \( (1,3) \) and \( (2,2),(2,3) \) — that is, box \( (1,3) \) has entry 2, box \( (2,2) \) has entry 1, and box \( (2,3) \) has entry 3. The inner corners of \( \mu = (2,1) \) (boxes we can remove to start a slide) are:
- Box \( (1,2) \): removing it leaves \( \mu' = (1,1) \). Valid inner corner.
- Box \( (2,1) \): removing it leaves \( \mu' = (2,0) = (2) \). Valid inner corner.
Slide 1: slide into \( (1,2) \). The empty cell is at \( (1,2) \). Look right: \( (1,3) \) has entry 2. Look below: \( (2,2) \) has entry 1. Since \( 1 < 2 \), slide the entry 1 from \( (2,2) \) into \( (1,2) \). The empty cell moves to \( (2,2) \). Now look right of \( (2,2) \): entry at \( (2,3) \) is 3. Look below \( (2,2) \): no box in row 3. So slide 3 from \( (2,3) \) into \( (2,2) \). The empty cell moves to \( (2,3) \), which is an outer corner of \( (3,3) \). Slide terminates. The new tableau has shape \( (3,2)/(1,1) \):
\[ T_1:\quad \begin{array}{ccc} \cdot & 1 & 2 \\ \cdot & 3 & \end{array} \]Slide 2: slide into \( (2,1) \) (the remaining inner corner of the current \( \mu' = (1,1) \)). Empty cell at \( (2,1) \). Right: \( (2,2) \) has entry 3. Below: no box in row 3. So slide 3 from \( (2,2) \) into \( (2,1) \). Empty cell moves to \( (2,2) \), which is an outer corner. Terminates. Shape is now \( (3,1)/(1,0) = (3,1)/(1) \):
\[ T_2:\quad \begin{array}{ccc} \cdot & 1 & 2 \\ 3 & & \end{array} \]Slide 3: slide into \( (1,1) \) (the remaining inner corner). Empty cell at \( (1,1) \). Right: \( (1,2) \) has entry 1. Below: \( (2,1) \) has entry 3. Since \( 1 < 3 \), slide 1 from \( (1,2) \) into \( (1,1) \). Empty cell moves to \( (1,2) \). Right: \( (1,3) \) has entry 2. Below: no box below \( (1,2) \) in the skew. Slide 2 from \( (1,3) \) into \( (1,2) \). Empty cell moves to \( (1,3) \), an outer corner. Terminates. We now have a straight-shape tableau of shape \( (2,1) \):
\[ \mathrm{rect}(T) = \begin{array}{|c|c|} \hline 1 & 2 \\ \hline 3 & \\ \hline \end{array} \]The rectification of \( T \) is the straight-shape SSYT with row 1 equal to \( 1, 2 \) and row 2 equal to \( 3 \). One can verify that performing the slides in a different order (e.g., first sliding into \( (2,1) \)) yields the same final result — this is the content of Schützenberger’s theorem.
Chapter 10: The Plactic Monoid and Knuth Equivalence
The plactic monoid is the free monoid on an ordered alphabet \( \{1, 2, \ldots, n\} \) (words in these letters) modulo the Knuth relations. Its discovery by Knuth (1970) and systematic study by Lascoux and Schützenberger (1981) revealed that RSK insertion is not just a bijection but a quotient map: the insertion tableau \( P(w) \) is an invariant of the Knuth equivalence class of the word \( w \), and conversely the Knuth class is exactly the fiber of the map \( w \mapsto P(w) \). This equips the space of words with algebraic structure that mirrors the structure of symmetric functions: Schur functions correspond to “plactic Schur elements,” and the Littlewood-Richardson rule admits a purely plactic proof.
- Knuth relation (K1): For \( x < y \leq z \), the subword \( yxz \) may be replaced by \( yzx \) (or vice versa): \( \ldots y\, x\, z \ldots \;\equiv_K\; \ldots y\, z\, x \ldots \).
- Knuth relation (K2): For \( x \leq y < z \), the subword \( xzy \) may be replaced by \( zxy \) (or vice versa): \( \ldots x\, z\, y \ldots \;\equiv_K\; \ldots z\, x\, y \ldots \).
The plactic monoid \( \mathrm{Pl}(A) \) is the quotient of the free monoid \( A^* \) by the congruence generated by these two relations. The equivalence class of a word \( w \) under Knuth equivalence is called its plactic class.
The two relations can be remembered mnemonically: (K1) says that when inserting a small element between two larger ones, the order among the larger ones can be swapped (row insertion bumps the leftmost element exceeding the inserted value); (K2) says that a “rise” and the element just before it can commute past each other. Both relations preserve the RSK insertion tableau, which is the key theorem.
Direct Knuth move: In \( u = 2\,1\,3 \), we have the subword \( 1\,3 \) at positions 2–3, and \( 2 \) at position 1. The triple \( (2,1,3) \) satisfies the condition for (K1) with \( x = 1, y = 2, z = 3 \): we have \( x < y \leq z \) (i.e., \( 1 < 2 \leq 3 \)), and the subword \( y\,x\,z = 2\,1\,3 \) can be replaced by \( y\,z\,x = 2\,3\,1 \). Indeed \( u = 2\,1\,3 \xrightarrow{(K1)} 2\,3\,1 = v \). So \( u \equiv_K v \) by a single Knuth move.
Verification via RSK: We compute \( P(u) \) and \( P(v) \) separately.
For \( u = 2,1,3 \): insert 2 into \( \emptyset \): \( P = \boxed{2} \). Insert 1: 1 bumps 2 in row 1, 2 goes to row 2. \( P = \begin{smallmatrix} 1 & \\ 2 & \end{smallmatrix} \) (column of shape \( (1,1) \)). Insert 3: 3 appends to end of row 1. \( P(u) = \begin{array}{|c|c|}\hline 1 & 3 \\ \hline 2 & \\ \hline\end{array} \).
For \( v = 2,3,1 \): insert 2: \( P = \boxed{2} \). Insert 3: 3 appends to row 1. \( P = \boxed{2\ 3} \). Insert 1: 1 bumps 2 (leftmost entry exceeding 1 in row 1), 2 goes to row 2. Then 3 stays in row 1 column 2. \( P(v) = \begin{array}{|c|c|}\hline 1 & 3 \\ \hline 2 & \\ \hline\end{array} \).
Indeed \( P(u) = P(v) \) — both equal the SSYT \( \begin{array}{|c|c|}\hline 1 & 3 \\ \hline 2 & \\ \hline\end{array} \). The recording tableaux differ: \( Q(u) = \begin{array}{|c|c|}\hline 1 & 3 \\ \hline 2 & \\ \hline\end{array} \) and \( Q(v) = \begin{array}{|c|c|}\hline 1 & 2 \\ \hline 3 & \\ \hline\end{array} \), distinguishing the two words within their plactic class.
The plactic monoid also connects to the theory of crystal bases (Kashiwara, 1990). Each Knuth equivalence class is a crystal graph component: the crystal operators \( e_i, f_i \) (raising and lowering operators for a quantum group at \( q=0 \)) act on words by locally modifying them in a way that preserves or moves between plactic classes. The crystal graph on words of content \( \mu \) has connected components indexed by SSYT, providing a canonical basis for representations of \( \mathrm{GL}(n) \) that behaves optimally with respect to the RSK correspondence.
Chapter 11: The Omega Involution — A Systematic Treatment
The involution \( \omega : \Lambda \to \Lambda \) was introduced briefly in Chapter 2 as the algebra map sending \( e_k \mapsto h_k \). Its effects ripple throughout symmetric function theory: it swaps the two Pieri rules, conjugates Schur functions, reverses the sign of odd power sums, and provides a uniform way to generate “dual” identities. Understanding \( \omega \) systematically — not just as an algebraic curiosity but as a structural symmetry — is essential for reading the literature and for applying symmetric functions to representation theory, where \( \omega \) corresponds to tensoring with the sign character.
- Elementary and complete: \( \omega(e_k) = h_k \) and \( \omega(h_k) = e_k \) for all \( k \geq 0 \). For products: \( \omega(e_\lambda) = h_\lambda \) and \( \omega(h_\lambda) = e_\lambda \).
- Power sums: \( \omega(p_k) = (-1)^{k-1} p_k \). For products: \( \omega(p_\lambda) = \varepsilon(\lambda) p_\lambda \), where \( \varepsilon(\lambda) = (-1)^{|\lambda| - \ell(\lambda)} \) is the sign of a permutation of cycle type \( \lambda \).
- Schur functions: \( \omega(s_\lambda) = s_{\lambda'} \), where \( \lambda' \) is the conjugate partition.
- Monomial: \( \omega(m_\lambda) = \sum_{\mu} (\text{entry of the inverse Kostka-like matrix}) m_\mu \); the formula is not as clean, but \( \omega(m_{(k)}) = (-1)^{k-1} m_{(1^k)} + \cdots \) in general.
Effect on \( p_k \): Use the Newton identity \( p_k = \sum_{j=1}^k (-1)^{j-1} e_j p_{k-j} + (-1)^{k-1} k e_k \), which expresses \( p_k \) in terms of \( e_j \) and \( p_j \) for smaller \( j \). Applying \( \omega \) and using \( \omega(e_j) = h_j \), we get \( \omega(p_k) = \sum_j (-1)^{j-1} h_j \omega(p_{k-j}) + (-1)^{k-1} k h_k \). By induction (the base case \( p_1 = e_1 = h_1 \), so \( \omega(p_1) = h_1 = p_1 = (-1)^0 p_1 \) ✓) and the dual Newton identity \( p_k = \sum_{j=1}^k (-1)^{j-1} h_j p_{k-j} + (-1)^{k-1} k h_k \), one checks that \( \omega(p_k) = (-1)^{k-1} p_k \) satisfies the recursion.
\[ \omega(s_\lambda) = \det(\omega(e_{\lambda'_i - i + j})) = \det(h_{\lambda'_i - i + j}). \]This is precisely the Jacobi-Trudi determinant for \( s_{\lambda'} \). Hence \( \omega(s_\lambda) = s_{\lambda'} \). \( \square \)
Method 1 — Conjugation. The partition \( (3,1) \) has Young diagram with row lengths \( 3, 1 \). Reading column lengths (from left to right): column 1 has 2 boxes (from rows 1 and 2), column 2 has 1 box (row 1 only), column 3 has 1 box (row 1 only). Therefore \( (3,1)' = (2,1,1) \). By the theorem, \( \omega(s_{(3,1)}) = s_{(3,1)'} = s_{(2,1,1)} \). \( \checkmark \)
\[ \omega(s_{(3,1)}) = \omega(h_3 h_1 - h_4) = e_3 e_1 - e_4 = e_{(3,1)} - e_{(4)}. \]Now we compute \( s_{(2,1,1)} \) using the dual Jacobi-Trudi (in the \( e \)-basis). We have \( \lambda = (2,1,1) \) with \( \lambda' = (3,1) \), so \( \ell(\lambda') = 2 \):
\[ s_{(2,1,1)} = \det\begin{pmatrix} e_{\lambda'_1 - 1 + 1} & e_{\lambda'_1 - 1 + 2} \\ e_{\lambda'_2 - 2 + 1} & e_{\lambda'_2 - 2 + 2} \end{pmatrix} = \det\begin{pmatrix} e_3 & e_4 \\ e_0 & e_1 \end{pmatrix} = e_3 e_1 - e_4. \]So \( s_{(2,1,1)} = e_3 e_1 - e_4 = e_{(3,1)} - e_{(4)} \), and \( \omega(s_{(3,1)}) = e_{(3,1)} - e_{(4)} = s_{(2,1,1)} \). \( \checkmark \)
Both methods agree. The numerical check: \( f^{(3,1)} = 3 \) (hook lengths of \( (3,1) \) are \( 4,2,1,1 \), product 8, \( f^{(3,1)} = 4!/8 = 3 \)) and \( f^{(2,1,1)} = 3 \) (hook lengths of \( (2,1,1) \) are also \( 4,2,1,1 \) by self-duality of the hook structure under conjugation — since \( h(i,j;\lambda) = h(j,i;\lambda') \), the hook length multisets of \( \lambda \) and \( \lambda' \) are equal). So both shapes have the same number of SYT, consistent with \( \omega \) being an isometry: \( f^{\lambda'} = \langle s_{\lambda'}, s_{\lambda'} \rangle^{1/2} = \dim V^{\lambda'} = \dim V^\lambda = f^\lambda \) (both Specht modules are related by tensoring with the sign character, which is an automorphism of \( S_n \)-rep theory, preserving dimensions).
A self-conjugate partition \( \lambda = \lambda' \) gives \( \omega(s_\lambda) = s_\lambda \), i.e., \( s_\lambda \) is fixed by \( \omega \). Such Schur functions correspond to representations \( V^\lambda \) isomorphic to \( V^\lambda \otimes \mathrm{sgn} \), meaning \( V^\lambda \) is self-dual under the sign twist. For \( n \leq 5 \), the self-conjugate partitions are \( (1), (2,1), (3,2,1), (2,1), (3,1,1,1), \ldots \) — their Specht modules admit a symmetric bilinear form preserved by the full action of \( S_n \), a fact used in the construction of orthogonal representations.
The generating function for \( h_k \) is \( \sum_k h_k t^k = \prod_i (1-x_i t)^{-1} \), and for \( e_k \) is \( \sum_k e_k t^k = \prod_i (1+x_i t) \). Applying \( \omega \) swaps these two generating functions:
\[ \omega\!\left(\sum_{k \geq 0} h_k t^k\right) = \sum_{k \geq 0} e_k t^k, \qquad \omega\!\left(\sum_{k \geq 0} e_k t^k\right) = \sum_{k \geq 0} h_k t^k. \]Taking logarithms:
\[ \omega\!\left(\sum_{k \geq 1} \frac{p_k}{k} t^k\right) = \sum_{k \geq 1} \frac{(-1)^{k-1} p_k}{k} t^k. \]Since \( \omega \) is an algebra map and \( p_k \) are algebraically independent over \( \mathbb{Q} \), we may apply \( \omega \) term by term inside the sum (which is really a formal power series identity, not requiring convergence). Matching coefficients of \( t^k/k \):
\[ \omega(p_k) = (-1)^{k-1} p_k. \quad \checkmark \]This derivation is clean and shows why the signs \( (-1)^{k-1} \) arise: they are exactly the signs from expanding \( \log(1+x_i t) = x_i t - x_i^2 t^2/2 + x_i^3 t^3/3 - \cdots \).
Chapter 12: The Cauchy Identity via RSK
The Cauchy identity
\[ \sum_\lambda s_\lambda(\mathbf{x}) s_\lambda(\mathbf{y}) = \prod_{i,j \geq 1} \frac{1}{1-x_i y_j} \]appears in Chapter 4 as a consequence of Schur orthonormality. Here we give a direct combinatorial proof via RSK, which is both more elementary and more illuminating: it exhibits the identity as a weight-preserving bijection between two naturally defined sets, with both sides counting the same objects in different ways.
This is the generating function for pairs \( (P, Q) \) of SSYT of the same shape, where \( P \) is weighted by \( \mathbf{x} \) and \( Q \) by \( \mathbf{y} \).
\[ \prod_{i,j \geq 1} \frac{1}{1-x_i y_j} = \prod_{i,j} \sum_{a_{ij} \geq 0} (x_i y_j)^{a_{ij}} = \sum_{A = (a_{ij})} \prod_{i,j} x_i^{a_{ij}} y_j^{a_{ij}}. \]Collecting powers: \( \prod_{i,j} x_i^{a_{ij}} y_j^{a_{ij}} = \prod_i x_i^{\sum_j a_{ij}} \cdot \prod_j y_j^{\sum_i a_{ij}} = \mathbf{x}^{\mathrm{rowsum}(A)} \mathbf{y}^{\mathrm{colsum}(A)} \). So the left-hand side is the generating function for matrices \( A = (a_{ij})_{i,j \geq 1} \) of non-negative integers with finite total sum, where the weight of \( A \) is \( \mathbf{x}^{\mathrm{rowsum}(A)} \mathbf{y}^{\mathrm{colsum}(A)} \) (row \( i \) contributes to the power of \( x_i \) and column \( j \) contributes to the power of \( y_j \)).
\[ A \;\longleftrightarrow\; (P, Q), \]where \( A \) ranges over non-negative integer matrices with finite total sum \( N \), and \( (P, Q) \) ranges over pairs of SSYT of the same shape \( \lambda \vdash N \). The weights match: the row sums of \( A \) equal the content of \( Q \) (so \( \mathbf{x}^{\mathrm{rowsum}(A)} = \mathbf{x}^{\mathrm{wt}(Q)} \)), and the column sums of \( A \) equal the content of \( P \) (so \( \mathbf{y}^{\mathrm{colsum}(A)} = \mathbf{y}^{\mathrm{wt}(P)} \)). (Conventions: in the SSYT version of RSK, we build \( P \) by inserting the entries of the biword of \( A \) in column-reading order, and \( P \) encodes the column data while \( Q \) encodes the row data.)
\[ \prod_{i,j} \frac{1}{1-x_i y_j} = \sum_A \mathbf{x}^{\mathrm{rowsum}(A)} \mathbf{y}^{\mathrm{colsum}(A)} = \sum_\lambda \sum_{\substack{P,Q \text{ SSYT} \\ \mathrm{shape} = \lambda}} \mathbf{x}^{\mathrm{wt}(Q)} \mathbf{y}^{\mathrm{wt}(P)} = \sum_\lambda s_\lambda(\mathbf{x}) s_\lambda(\mathbf{y}). \quad \square \]All \( 2 \times 2 \) matrices \( A = \begin{pmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix} \) with \( a_{ij} \geq 0 \) and \( a_{11}+a_{12}+a_{21}+a_{22} = 2 \). There are \( \binom{2+3}{3} = 10 \) such matrices (stars and bars with 4 cells summing to 2). Each has weight \( x_1^{a_{11}+a_{12}} x_2^{a_{21}+a_{22}} y_1^{a_{11}+a_{21}} y_2^{a_{12}+a_{22}} \).
Under RSK, these 10 matrices correspond to pairs \( (P,Q) \) of SSYT of the same shape \( \lambda \vdash 2 \) with entries in \( \{1,2\} \). The shapes are \( (2) \) and \( (1,1) \).
- Shape \( \lambda = (2) \): \( s_{(2)}(x_1,x_2) = h_2(x_1,x_2) = x_1^2+x_1 x_2+x_2^2 \), and similarly \( s_{(2)}(y_1,y_2) = y_1^2 + y_1 y_2 + y_2^2 \). The pair \( (s_{(2)}, s_{(2)}) \) contributes 9 monomials of the form \( x_i^{a_i} y_j^{b_j} \) with \( a_1+a_2 = 2, b_1+b_2 = 2 \) (all of the same-shape SSYT pairs of shape \( (2) \)).
- Shape \( \lambda = (1,1) \): \( s_{(1,1)}(x_1,x_2) = e_2(x_1,x_2) = x_1 x_2 \), and \( s_{(1,1)}(y_1,y_2) = y_1 y_2 \). This contributes the single monomial \( x_1 x_2 y_1 y_2 \).
On the right side of the Cauchy identity restricted to \( x_1,x_2,y_1,y_2 \) and degree \( N=2 \):
\[ s_{(2)}(x)s_{(2)}(y) + s_{(1,1)}(x)s_{(1,1)}(y) = (x_1^2+x_1 x_2+x_2^2)(y_1^2+y_1 y_2+y_2^2) + x_1 x_2 \cdot y_1 y_2. \]On the left side, the degree-2 part of \( \prod_{i,j=1}^2 (1-x_i y_j)^{-1} \) is:
\[ \sum_{\substack{a_{ij} \geq 0 \\ \sum a_{ij} = 2}} x_1^{a_{11}+a_{12}} x_2^{a_{21}+a_{22}} y_1^{a_{11}+a_{21}} y_2^{a_{12}+a_{22}}. \]One can directly verify that these two expressions are equal as polynomials in \( x_1,x_2,y_1,y_2 \), for instance by checking that the coefficient of each monomial \( x_1^{r_1} x_2^{r_2} y_1^{c_1} y_2^{c_2} \) (with \( r_1+r_2 = c_1+c_2 = 2 \)) matches on both sides — each such monomial corresponds to exactly the RSK pairs compatible with the given row and column sums. \( \checkmark \)
Appendix: Key Formulas and Summary Tables
Summary of Symmetric Function Bases
The following table collects the standard bases of \( \Lambda^n \), their generating functions, and the key algebraic structure they reveal.
| Basis | Notation | Generating function | Key property |
|---|---|---|---|
| Monomial | \( m_\lambda \) | (none simple) | Canonical, integer coefficients |
| Elementary | \( e_\lambda \) | \( \prod_i(1+x_i t) = \sum_k e_k t^k \) | \( \Lambda = \mathbb{Z}[e_1,e_2,\ldots] \) |
| Complete homogeneous | \( h_\lambda \) | \( \prod_i \frac{1}{1-x_i t} = \sum_k h_k t^k \) | \( \Lambda = \mathbb{Z}[h_1,h_2,\ldots] \) |
| Power sum | \( p_\lambda \) | (product of \( \sum_i x_i^k \)) | Characters: \( \Lambda_\mathbb{Q} = \mathbb{Q}[p_1,p_2,\ldots] \) |
| Schur | \( s_\lambda \) | \( \sum_T x^{\mathrm{wt}(T)} \) over SSYT | Orthonormal, positive, RSK |
Transition Matrices for \( n = 3 \)
In dominance order \( (3) >_\mathrm{dom} (2,1) >_\mathrm{dom} (1^3) \), the transition matrices are:
\[ K = \begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 0 & 0 & 1 \end{pmatrix}, \qquad K^{-1} = \begin{pmatrix} 1 & -1 & 1 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{pmatrix}. \]\[ \chi = \begin{pmatrix} 1 & 1 & 1 \\ 2 & 0 & -1 \\ 1 & -1 & 1 \end{pmatrix} \](rows: \( \lambda = (3),(2,1),(1^3) \); columns: \( \mu = (1^3),(2,1),(3) \)).
The \( z_\mu \) values: \( z_{(3)} = 3 \), \( z_{(2,1)} = 2 \), \( z_{(1^3)} = 6 \).
Key Identities
The following identities hold in \( \Lambda \) (with \( h_0 = e_0 = 1 \), \( h_k = e_k = 0 \) for \( k < 0 \)):
\[ \left(\sum_{k \geq 0} h_k t^k\right) \left(\sum_{k \geq 0} e_k (-t)^k\right) = 1. \]\[ h_n = \sum_{k=1}^n (-1)^{k-1} e_k h_{n-k}, \qquad p_n = \sum_{k=1}^n (-1)^{k-1} e_k p_{n-k} + (-1)^{n-1} n e_n. \]\[ s_\lambda = \det(h_{\lambda_i - i + j})_{1 \leq i,j \leq \ell(\lambda)}, \qquad s_\lambda = \det(e_{\lambda'_i - i + j})_{1 \leq i,j \leq \ell(\lambda')}. \]Involution: \( \omega(e_k) = h_k \), \( \omega(h_k) = e_k \), \( \omega(p_k) = (-1)^{k-1} p_k \), \( \omega(s_\lambda) = s_{\lambda'} \).
\[ \sum_\lambda s_\lambda(x) s_\lambda(y) = \prod_{i,j} \frac{1}{1-x_i y_j} = \sum_\lambda h_\lambda(x) m_\lambda(y). \]\[ s_\lambda \cdot h_n = \sum_{\mu: \mu/\lambda \text{ horiz. strip}} s_\mu, \qquad s_\lambda \cdot e_n = \sum_{\nu: \nu/\lambda \text{ vert. strip}} s_\nu. \]\[ s_\lambda \cdot p_n = \sum_{R \text{ border strip of size } n} (-1)^{\mathrm{ht}(R)} s_{\lambda \cup R}. \]\[ s_\mu \cdot s_\nu = \sum_\lambda c^\lambda_{\mu\nu} s_\lambda, \quad c^\lambda_{\mu\nu} = \#\{\text{ballot SSYT of shape } \lambda/\mu, \text{ content } \nu\}. \]\[ \mathrm{ch}(V^\lambda) = s_\lambda, \qquad \chi^\lambda(\mu) = z_\mu \langle s_\lambda, p_\mu \rangle. \]\[ f^\lambda = \frac{n!}{\prod_{(i,j) \in \lambda} h(i,j)}, \quad h(i,j) = \lambda_i - j + \lambda'_j - i + 1. \]Worked Example: Complete Analysis of \( \lambda = (2,2) \)
To illustrate how the various parts of the theory fit together for a single partition, we carry out a complete analysis of \( \lambda = (2,2) \vdash 4 \).
1. Hook-length formula. The hooks are: \( h(1,1) = 2-1+2-1+1 = 3 \), \( h(1,2) = 2-2+1-1+1 = 1 \), \( h(2,1) = 2-1+2-2+1 = 2 \), \( h(2,2) = 2-2+1-2+1 = 0 \)… wait: \( \lambda' = (2,2) \) (the shape is symmetric). So \( h(2,2) = \lambda_2 - 2 + \lambda'_2 - 2 + 1 = 0 + 2 - 2 + 1 = 1 \). Correcting: hooks are 3, 1, 2, 1. Product: \( 3 \cdot 1 \cdot 2 \cdot 1 = 6 \). So \( f^{(2,2)} = 4!/6 = 24/6 = 4 \)… but we said \( f^{(2,2)} = 2 \) earlier. Let us recheck.
For \( \lambda = (2,2) \), \( \lambda' = (2,2) \). Box \( (1,1) \): \( h = \lambda_1 - 1 + \lambda'_1 - 1 + 1 = 2-1+2-1+1 = 3 \). Box \( (1,2) \): \( h = \lambda_1 - 2 + \lambda'_2 - 1 + 1 = 0 + 2 - 1 + 1 = 2 \). Box \( (2,1) \): \( h = \lambda_2 - 1 + \lambda'_1 - 2 + 1 = 1 + 2 - 2 + 1 = 2 \). Box \( (2,2) \): \( h = \lambda_2 - 2 + \lambda'_2 - 2 + 1 = 0 + 2 - 2 + 1 = 1 \). Product: \( 3 \cdot 2 \cdot 2 \cdot 1 = 12 \). So \( f^{(2,2)} = 24/12 = 2 \) ✓. There are 2 standard Young tableaux of shape \( (2,2) \):
\[ T_1 = \begin{array}{|c|c|}\hline 1 & 2 \\\hline 3 & 4 \\\hline\end{array}, \qquad T_2 = \begin{array}{|c|c|}\hline 1 & 3 \\\hline 2 & 4 \\\hline\end{array}. \]2. Schur function. \( s_{(2,2)} = h_2^2 - h_3 h_1 \) (from the Jacobi-Trudi \( 2\times 2 \) determinant: \( s_{(2,2)} = \det\begin{pmatrix} h_2 & h_3 \\ h_1 & h_2 \end{pmatrix} = h_2^2 - h_3 h_1 \)).
In 2 variables: \( h_2 = x_1^2 + x_1 x_2 + x_2^2 \), \( h_3 h_1 = (x_1^3 + x_1^2 x_2 + x_1 x_2^2 + x_2^3)(x_1+x_2) \). Computing \( h_2^2 - h_3 h_1 \) in 2 variables gives \( s_{(2,2)}(x_1,x_2) = x_1^2 x_2^2 \). In 3 variables: \( s_{(2,2)} = m_{(2,2)} + m_{(2,1,1)} \). The Kostka number \( K_{(2,2),(2,2)} = 1 \) (the unique SSYT is \( \begin{smallmatrix}1&1\\2&2\end{smallmatrix} \)) and \( K_{(2,2),(2,1,1)} = 1 \) (the unique SSYT is \( \begin{smallmatrix}1&1\\2&3\end{smallmatrix} \)).
3. Character value. \( \chi^{(2,2)}(\mu) \) for \( \mu \vdash 4 \) using the Murnaghan-Nakayama rule. For \( \mu = (4) \): add one border strip of size 4 to \( \emptyset \) to reach \( (2,2) \). The shape \( (2,2) \) itself would need to be a border strip — but \( (2,2) \) contains a \( 2 \times 2 \) square, so it is NOT a border strip. Hence \( \chi^{(2,2)}(4) = 0 \) (confirmed by the table above). For \( \mu = (1^4) \): \( \chi^{(2,2)}(1^4) = f^{(2,2)} = 2 \) (number of SYT).
4. RSK shape. The 4 permutations in \( S_4 \) with RSK shape \( (2,2) \) can be enumerated. They satisfy the RSK bijection \( w \mapsto (P,Q) \) with both \( P,Q \) standard of shape \( (2,2) \). Since \( f^{(2,2)} = 2 \), there are \( 2^2 = 4 \) such permutations. One of them is \( w = 3142 \) (computed earlier).
5. Representation theory. The Specht module \( V^{(2,2)} \) is a 2-dimensional irreducible \( S_4 \)-representation. It is the representation whose character satisfies \( \chi^{(2,2)}(1^4) = 2, \chi^{(2,2)}(4) = 0, \chi^{(2,2)}(2^2) = 2, \chi^{(2,2)}(3,1) = -1, \chi^{(2,2)}(2,1^2) = 0 \). Note that \( \lambda = (2,2) \) is self-conjugate (\( \lambda' = (2,2) \)), so \( \omega(s_{(2,2)}) = s_{(2,2)'} = s_{(2,2)} \). This means \( V^{(2,2)} \) is fixed under tensoring with the sign representation: \( V^{(2,2)} \otimes \mathrm{sgn} \cong V^{(2,2)} \). The 2-dimensional irrep can be explicitly constructed: it acts on the space spanned by the two SYT \( T_1, T_2 \) above, with the \( S_4 \)-action given by the Young-naturality condition.
This unified example demonstrates how partitions serve as the organizing principle across the four aspects of the theory: the hook-length formula (combinatorial dimension count), the Schur function (the generating function encoding all SSYT), the character table (via Frobenius), and the RSK correspondence (bijective proof of the dimension formula). The remarkable fact is that these four perspectives are not merely compatible — they are four different windows onto the same underlying mathematical structure.
Stanley-Stembridge conjecture (\( e \)-positivity of unit interval orders): As stated in Chapter 8, the chromatic symmetric function of any incomparability graph of a unit interval order is conjectured to expand with non-negative coefficients in the \( e \)-basis. The conjecture was partially proved for specific graph families (paths, cycles, complete bipartite graphs), and Shareshian-Wachs introduced a refinement to the chromatic quasisymmetric function \( X_G(x,t) \) that appears to be \( e \)-positive as a polynomial in \( t \). Brosnan and Chow (2018) proved the Shareshian-Wachs conjecture for so-called abelian Hessenberg varieties by identifying \( X_G(x,t) \) with the cohomology of Hessenberg varieties equipped with a natural torus action, proving positivity geometrically.
Positivity of Kronecker coefficients: The Kronecker coefficients \( g(\lambda, \mu, \nu) \) are defined by the internal product \( s_\lambda * s_\mu = \sum_\nu g(\lambda,\mu,\nu) s_\nu \) (where \( * \) is the operation dual to the coproduct), or equivalently as multiplicities in the tensor product of two \( S_n \)-representations: \( V^\lambda \otimes V^\mu \cong \bigoplus_\nu g(\lambda,\mu,\nu) V^\nu \). Unlike LR coefficients, no combinatorial rule for Kronecker coefficients is known in general. Finding such a rule is a major open problem. It is known that \( g(\lambda,\mu,\nu) \in \mathbb{Z}_{\geq 0} \) (from representation theory), but no combinatorial interpretation has been established.
Schubert calculus in other types: The Grassmannian \( \mathrm{Gr}(k,n) \) corresponds to type A. Analogous theories exist for Lagrangian Grassmannians (type C), orthogonal Grassmannians (types B/D), and exceptional groups (types G, F, E). The structure constants in these cohomology rings generalize LR coefficients and remain less understood. The \( K \)-theory (replacing cohomology) version leads to \( K\)-theoretic Schubert calculus with positive (but signed in general) structure constants, studied by Lam, Postnikov, Pylyavskyy, and others.
Combinatorial interpretation of Macdonald polynomials: While Haiman’s theorem proves the positivity of \( \tilde{K}_{\lambda\mu}(q,t) \), it does not give a combinatorial formula for the coefficients as integers. Haglund, Haiman, and Loehr (2005) found a combinatorial formula for the monomial expansion of \( \tilde{H}_\lambda(x;q,t) \) in terms of “inv” and “maj” statistics on fillings of the Young diagram, but extending this to other bases and understanding the representation-theoretic structure combinatorially remains an active area.
