18.315 Combinatorial Theory (Fall 2003)

Instructor: Igor Pak

Class schedule: MWF 1-2, 2-108.
Office hours: 2-390, M 2-3, to be confirmed

Grading: There will be weekly home assignments graded by the instructor. In the last week of classes (tentatively, on Monday Dec 8) there will one "final" home assignment given for 48 hours. The grade will be weighted 40% of the weekly home assignments and 60% of the "final" home assignment.

Difficulty: This is a graduate level course, although it should be accessible to some advance undergraduate students. We assume familiarity with basic methods in Combinatorics.

Textbooks:
R. P. Stanley, Enumerative Combinatorics, vol. I, II, Cambridge University Press, 1999
B. Bollobas, Modern Graph Theory (Graduate Texts in Mathematics), Springer, 1998
Both are available at Quantum Books
Additional reading will be posted on this page.

Content

The unifying theme of the course is Bijective Combinatorics. We cover a variety of topics in Enumerative Combinatorics (understood in a modern, rather loose sense) with the emphasis on the structure of combinatorial objects, and direct combinatorial proofs.

Partitions:
- Basic tools, Durfee square arguments
- Euler's Pentagonal Thm
- Schur and Lebesgue identities
- Jacobi triple product identity
- Rogers-Ramanujan identities
- Involution principle
- Asymptotics and applications
Young Tableaux:
- Stanley's hook content formula (HCF):
  - Hillman-Grassl bijection
  - geometric bijection
  - RSK and duality property
- Hook length formula (HLF):
  - reduction from HCF
  - NPS proof + random generation
  - probabilistic proof + Kerov's extension
- Bender-Knuth transformations
  - Tableaux switching
  - Schutzenberger involution
- LR tableaux, hives, BZ-triangles
- Rim hook bijection

Graphs and spanning trees:
- Cayley formula (several bijective proofs)
- Tutte polynomial:
  - several equivalent definitions
  - internal and external activities, invariance,
  - recursive formula for a complete graph
  - evaluations (chromatics polynomial, acyclic orientations, etc.)
  - plane graphs (several evaluations)
- Hyperplane arrangements
- Knot and link invariants (Kaufmann's bracket, Jones polynomial)
- generating random spanning trees (algorithms of Aldous and Wilson)
- sandpiles

Tilings:
- domino tilings:
  - Thurston's algorithm
  - Pfaffian orientations, Kastelyn determinants
  - domino tilings of an Aztec diamond
- ribbon tilings
- T-tetromino tilings

Additional Reading:

Partitions:
- Igor Pak, Partition bijections, a survey, available here.
- George Andrews, The Theory of Partitions, (Encyclopedia of Mathematics and its Applications, vol. 2) Addison-Wesley, Reading, MA, 1976; Reissued in paperback by Cambridge University Press, 1998.
- G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford University Press, Oxford, England, 1979
Young tableaux:
- B. Sagan, The Symmetric Group (Second Ed.), Springer-Verlag, 2001.
- W. Fulton, Young Tableaux with Applications to Representation Theory and Geometry, Cambridge University Press, New York, 1997.
Graphs, etc. :
- Anders Bjorner et al., Oriented Matroids, Cambridge University Press, 2001.
- D.J.A. Welsh, Complexity: Knots, Colourings and Counting, Cambridge University Press, LMS Lecture Notes Series, 1993.

Papers on tilings are available here.

Click here to return to Igor Pak Home Page.

To e-mail me click here and delete .zzz
Put 18.315 in the Subject line.

Last updated 9/2/2003