Math 192 - Algebraic Combinatorics

Math 192 - Algebraic Combinatorics - Fall 2006

Lectures: Tuesday and Thursday 10-11:30am, in Science Center 112 (Note: new room! It's next to the old one).

Lecturer: Lauren Williams (office Science Center 432, e-mail lauren@math.harvard.edu)

Office Hours: Monday 4-5pm or by appointment, at Science Center 432

Course Assistant: Joel Brewster Lewis

Course description

This course is an introductory course in algebraic combinatorics. No prior knowledge of combinatorics is expected, but I will assume a familiarity with linear algebra and finite groups. The course is meant to be challenging but also a lot of fun. Rigorous mathematical proofs are expected.

There will be problem sets every week or so (worth 60%), an in-class exam (10%), and a final project (30%) in lieu of a final exam.

The first half of the course will develop some methods in enumerative combinatorics. It will cover the following topics:

The involution principle and the Gessel-Viennot Lemma.
The Mobius function and Mobius inversion on posets.
Rational (ordinary) generating functions.
Exponential generating functions.
Partitions and their generating functions.
The Matrix-tree theorem.
Hypergeometric summation?

The second half of the course will focus on interesting topics in algebraic combinatorics and applications of the aforementioned methods. These topics may include:

Catalan numbers (combinatorial interpretations, and the connection with lattice paths and orthogonal polynomials).
Symmetric functions (including Schur functions, Young tableaux, and the RSK algorithm).
Counting polynomials (such as the chromatic and Tutte polynomials, knot polynomials, the Ehrhardt polynomial of a polytope).
Models from statistical physics (such as the dimer problem and perfect matchings, the Ising problem and Eulerian subgraphs, and square ice).
Somos sequences and Laurent phenomenon?

Lectures

Lecture 1 (Sept. 19): The Gessel-Viennot Lemma. Applications to linear algebra and to rhombus tilings of a hexagon.

Lecture 2 (Sept. 21): Catalan numbers, another application of Gessel-Viennot, the Involution Principle. Started ordinary generating functions.

Lecture 3 (Sept. 26): More on ordinary generating functions. Exponential generating functions: the compositional formula, the exponential formula. Application to counting connected graphs on n vertices.

Lecture 4 (Sept. 28): Review of compositional formula. Enumeration of trees, and Lagrange inversion.

Lecture 5 (Oct. 3): Finish Lagrange inversion. Partitions and their generating functions.

Lecture 6 (Oct. 5): Guest lecture by Seth Sullivant! Posets (partially ordered sets), Mobius inversion.

Lecture 7 (Oct. 10): Eulerian tours in directed graphs

Lecture 8 (Oct. 12): The Matrix Tree Theorem and applications

Lecture 9 (Oct. 17): Walks on graphs, random walks on graphs.

Midterm! (Oct. 19):

Lecture 10 (Oct. 24): Go over the exam, introduce chromatic polynomial of a graph.

Lecture 11 (Oct. 26): Chromatic polynomial, Tutte polynomial.

Lecture 12 (Oct. 31): More on the Tutte polynomial. Matroids!

Lecture 13 (Nov. 2): A little more on the Tutte polynomial. Knots and knot polynomials.

Lecture 14 (Nov. 7): More on knot polynomials: the bracket and Jones polynomial. Start symmetric functions.

Lecture 15 (Nov. 9): Elementary and monomial symmetric functions; the fundamental theorem of symmetric functions.

Lecture 16 (Nov. 14): Homogeneous symmetric functions and Schur functions.

Lecture 17 (Nov. 16): The RSK correspondence

Lecture 18 (Nov. 21): Plane partitions (MacMahon's formula) and Hook length formulae

Happy Thanksgiving (Nov. 23)

Lecture 19 (Nov. 28): Perfect matchings, Pfaffians, and the dimer problem

Lecture 20 (Nov. 30): The dimer problem, continued

Lecture 21 (Dec. 5): Square ice, the 6-vertex model, and alternating sign matrices

Lecture 22 (Dec. 7): Permutation statistics, Eulerian numbers, asymmetric exclusion process.

Lecture 23 (Dec. 12): Polya Theory (enumeration under group action)

Lecture 24 (Dec. 14): Student presentations

Lecture 25 (Dec. 19): Student presentations

Problem Sets

Problem Set 1

Problem Set 2 (due October 12)

Problem Set 3 (due October 24 -- extended to Oct. 27)

Problem Set 4 (due November 7)

Problem Set 5 (due November 16)

Problem Set 6 (due November 30)

Problem Set 7 (due December 12)

Final Project

Here is a list of suggestions for your final project. You need to give an in-class presentation at the end of December (of approximately 30 minutes) and write a paper in Latex (of approximately 5 pages) which is due at the end of reading period in January.