Algebraic Combinatorics
Spring term 2012
General
Information
- Instructor: Anders Björner,
bjorner(at)math.kth.se
- Level: Graduate, course number FSF 3702
- Prerequsites: Basic courses in algebra and
combinatorics. Mathematical maturity.
- Place: Seminar Room 3721, Mathematics Dept, KTH,
Lindstedtsvägen 25, 7th floor
- Time: Most Tuesdays, 13:15 - 15:00 and some Thursdays
15.15 - 17.00.
- Dates: February 7, 14,
21, 28; March 1, 6, 20, 22, 27, 29; April 10, 17, 24; May 8.
- Examination: There
will be a take-home exam at the end of the course. Grades:
Pass/Fail.
- Problem sets: Set
#1, Set #2
Course content
Algebraic methods are very important in many areas of
combinatorial mathematics. On the other hand, there are several
situations in algebra and related fields where combinatorial
constructions hold the key to effective understanding. In this
course we will explore some classical material of these two kinds.
Also, glimpses of current research in the area will be given.
An important part of the course is formed by the theory of
symmetric functions, that is, polynomials that are invariant under
permutation of its indeterminates. This is a classic topic in
algebra, however the theory turns out to be of a mainly
combinatorial character. The ring L of symmetric
functions has a distinguished basis consisting of the Schur
functions. These are generating functions for certain
combinatorial gadgets called Young tableaux.
One reason for the broad mathematical significance of symmetric
functions is their role in representation theory and algebraic
geometry. Briefly, the representation ring of the symmetric groups
is isomorphic to L under an isomorphism that
carries the irreducible representations to the Schur functions. A
similar statement is true for the general linear groups.
Furthermore, the cohomology ring of a Grassman variety is
isomorphic to a quotient of L in a way that
matches Schubert cycles with Schur functions. Hence, in all these
situation the multiplication can be described in terms of Schur
functions, which means that ultimately it is governed entirely by
the combinatorics of Young tableaux.
On the combinatorial side the course will cover several topics
from classical enumerative combinatorics. This concerns in the
first instance partitions, permutations, plane partitions and
tableaux, where some of the highlights are the hook-length formula
for enumerating standard Young tableaux, MacMahon's enumeration
formula for plane partitions, the Robinson-Schensted-Knuth
correspondence between permutations (and more generally,
nonnegative integer matrices) and pairs of tableaux, jeu de
taquin, the theory of monotone subsequences, enumeration using
non-crossing lattice paths, etc
References
The indicated chapters of the
following books are recommended for side reading (not required).
- William Fulton, Young Tableaux, Cambridge Univ.
Press, 1997. [Part 1]
- Donald E. Knuth, The Art of Computer Programming,
Vol.3/Sorting and Searching, Addison-Wesley, 1973. [Chapter 5.1]
- Ian G. Macdonald, Symmetric functions and Hall
polynomials (Second Edition), Oxford Univ. Press, 1995. [Chapter 1]
- Bruce E. Sagan, The Symmetric Group (Second
Edition), Springer, 2001. [Chapters 3 and
4]
- Richard P. Stanley, Enumerative Combinatorics, Volume 2,
Cambridge Univ. Press, 1999. [Chapter 7]
Copies of these books have
been placed on reserve in the KTH mathematics library.
They can be read in the
library but may not be taken out. Ask the librarian for access to
the reserve shelf.
The following survey
papers shed some light on course material appearing in recent
research.
The web address is to a
program that computes products of Schur functions.
- W. Fulton, Eigenvalues, invariant factors, highest weights,
and Schubert calculus, Bull. Amer. Math. Soc. 37 (2000), 209-249. [See
especially section 9]
- R. Howe and S.T. Lee, Why should the Littlewood-Richardson
rule be true?, Bull. Amer. Math. Soc. 49 (2012), 187-236.
- http://young.sp2mi.univ-poitiers.fr/cgi-bin/form-prep/marc/LiE_form.act?action=LRR