Algebraic Combinatorics

Information | Content | Examination | References

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.