Algebra

Algebraic Combinatorics

Цели урока

Master the RSK bijection and Schensted's theorem on LIS
Understand the hook length formula and Kostka numbers
Know the definition of Coxeter groups and Bruhat order
Understand Kazhdan-Lusztig polynomials and their connection to flag geometry

Предварительные знания

Symmetric functions
Young diagrams
Groups and symmetry

Symmetric Functions

Patience sorting - sorting cards into piles - turned out to be the RSK bijection. The hook length formula of 1954 became the foundation for five different fields. Kazhdan-Lusztig polynomials introduced in 1979 predicted a geometric result, proved the next year by three independent methods. Algebraic combinatorics predicts before it proves.

Algorithms: RSK gives patience sorting which gives O(n log n) LIS - used in sequence alignment in bioinformatics
Physics: Kazhdan-Lusztig polynomials determine the canonical basis in IBM Research quantum groups
Combinatorial theory: Kostka numbers K_{lambda,mu} compute multiplicities in spectra of quantum spin chains
Geometry: P_{u,w}(q) encodes the topology of Schubert cells in flag varieties SL_n/B

One hundred years from Young to Kazhdan

Alfred Young in 1900 introduced diagrams for S_n-modules. In 1954 Frame, Robinson and Thrall proved the hook length formula f^lambda = n!/product h(i,j). Clive Schensted in 1961 established the LIS connection. Donald Knuth in 1970 generalized RSK to matrix correspondence. In 1979 David Kazhdan and George Lusztig introduced P_{u,w}. The following year Beilinson-Bernstein and Brylinski-Kashiwara proved nonnegativity independently, using D-modules and perverse sheaves.

RSK Correspondence and Hook Length Formula

1900. Alfred Young introduces tableaux. 1954. Three mathematicians prove the hook length formula. 1961. Knuth finds the bijection between permutations and pairs of tableaux. The O(n log n) LIS algorithm turns out to be a special case. Combinatorics and algorithms are one.

The O(n log n) LIS algorithm - patience sorting - is exactly what RSK does with the first row of tableau P. The number of piles of cards = LIS length = lambda_1(P). This is the only known 'simple' bijective reason the sorting algorithm works.

In the RSK correspondence sigma <-> (P,Q), what is the length of the first row of P?

Schensted's theorem: lambda_1(P) = LIS(sigma), lambda'_1(P) = LDS(sigma). The first row encodes the longest increasing subsequence.

Kostka Numbers and the Transition Matrix

Kostka numbers K_{lambda,mu} - the number of semistandard Young tableaux of shape lambda with content mu - are not arbitrary. They appear as multiplicities in GL(n)-representation decompositions and as transition matrix coefficients between bases of Lambda. Fundamental invariants, not random numbers.

K_{(2,1),mu} for all mu partitioning 3

Computing Kostka numbers

Partitions of 3: (3), (2,1), (1,1,1). SSYT of shape (2,1): K_{(2,1),(3)}=0 (cannot fill with content (3,0,0) while strictly increasing in columns), K_{(2,1),(2,1)}=1 (unique: 1 1 / 2), K_{(2,1),(1,1,1)}=2 (tableaux: 1 2/3 and 1 3/2). So s_(2,1) = m_(2,1) + 2*m_(1,1,1).

The Kostka number K_{lambda,mu} equals:

K_{lambda,mu} = |SSYT(lambda,mu)| and simultaneously = the multiplicity of weight mu in the GL(n)-module V_lambda. Formula: s_lambda = sum_mu K_{lambda,mu} m_mu.

Coxeter Groups and Bruhat Order

Coxeter groups are the algebraic skeleton of geometric symmetries. The symmetric group S_n is type A_{n-1}. The hyperoctahedral group is type B_n. The icosahedral group is type H_3. Each is specified by generators and relations. Coxeter theory is the language for all of this.

S_3 = Coxeter group of type A_2

Explicit example

S_3 = <s_1, s_2 | s_1^2=s_2^2=1, (s_1 s_2)^3=1>. Bruhat order: id < s_1, s_2 < s_1 s_2, s_2 s_1 < s_1 s_2 s_1 = s_2 s_1 s_2. Six elements, a six-level lattice. The KL polynomial P_{id,w_0}(q)=1 for S_3.

A Coxeter group is generated by reflections s_i with s_i^2=1. Which additional relations determine its structure?

Coxeter group: <s_1,...,s_n | s_i^2=1, (s_i s_j)^{m_{ij}}=1>. Coxeter matrix m_{ij} determines the type: A_n (m=3), B_n (m=4), G_2 (m=6), ...

Kazhdan-Lusztig Polynomials and Canonical Basis

1979. Kazhdan and Lusztig introduce strange polynomials. Their coefficients are nonneg - but this is not obvious from the definition. A decade is spent proving it. The outcome: connection to intersection cohomology, to the BBD theorem, to quantum groups. The polynomials turn out to be a window into the geometry of flag varieties.

The Kazhdan-Lusztig conjecture (1979, proved in 1980 by Beilinson-Bernstein and Brylinski-Kashiwara): the polynomials P_{u,w} have nonneg coefficients. The proof uses the BBD decomposition theorem for intersection cohomology - one of the deepest results in algebraic geometry.

The nonnegativity of coefficients of Kazhdan-Lusztig polynomials P_{u,w}(q):

Nonnegativity of coefficients of P_{u,w}(q) - theorem proved in 1980. Proof via geometry: coefficients = dimensions of IC sheaf cohomologies, which are nonneg.

Connections to other topics

Algebraic combinatorics unifies group theory, geometry, and algorithms.

alg-28-sym-func — extends

Итоги

RSK: sigma in S_n <-> (P,Q) SYT of same shape lambda partitioning n; lambda_1(P) = LIS(sigma), lambda'_1(P) = LDS(sigma)
Hook length formula: f^lambda = n!/product h(i,j) = dim irreducible S_n-module; sum (f^lambda)^2 = n!
Kostka numbers K_{lambda,mu} = |SSYT(lambda,mu)| = multiplicity of weight mu in GL(n)-module V_lambda
Coxeter group W = <s_i | s_i^2=1, (s_i s_j)^{m_{ij}}=1>; Bruhat partial order on W
KL polynomials P_{u,w}(q) with nonneg coefficients encode cohomologies of IC sheaves

Вопросы для размышления

Why does the RSK bijection between permutations and pairs of SYT explain the identity sum (f^lambda)^2 = n!?
How does the O(n log n) LIS algorithm relate to the first row of the RSK tableau?
What is the geometric meaning of the nonnegativity of Kazhdan-Lusztig polynomial coefficients?

Связанные уроки

alg-28-sym-func — RSK connects permutations to Schur functions
alg-27-lie-repr — S_n-representations via Young diagrams
alg-26-quantum-groups — Kazhdan-Lusztig polynomials from quantum groups