Algebraic Combinatorics
Spring term 2012
General Information
- Instructor: Anders Björner,
bjorner(at)math.kth.se
- Level: Graduate
- Prerequsites: Basic courses in algebra and
combinatorics. Mathematical maturity.
- Time: Tuesdays, 13:15 - 15:00, beginning February 7 [Note: No change of time,
just start postponed by one week.]
- Place: Seminar Room 3721, Mathematics Dept, KTH,
Lindstedtsvägen 25, 7th floor
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.
Examination
Three or four sets of problems will be assigned as take-home
examinations. Information about when the problem sets will be
available, as well as when solutions are due, will later be posted
on this web page.
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.