18.312 Algebraic Combinatorics

Spring 2011, Tuesday and Thursday 9:30-11am in room 2-151.

Instructor: Dr. Lionel Levine
Office Hours: Tue 12-1, Wed 1-2 in room 2-335.

Combinatorics encompasses not just the art of counting, but also analyzing the structure of discrete objects such as graphs, matroids and partially ordered sets. In algebraic combinatorics, one associates algebraic objects like groups, rings and vector spaces to combinatorial objects in order to reveal more of their structure.

Stern-Brocot tree
Identity element of the sandpile group

Textbook:

Supplementary textbooks: Purchasing these is optional. Van Lint and Wilson does not cover all of the topics we will cover, so if you want to be assured of having a textbook to reference for all topics, you should get all the books. These are great books that you will cherish for many years. But I know that textbooks aren't cheap, so I'll try to supplement with handouts to make it possible to get by on just the main text Van Lint and Wilson.

Syllabus:

Lecture 1 (Feb 1): necklaces and Fermat's little theorem. Notes (.tex ; .pdf) by Lou Odette.
Lecture 2 (Feb 3, guest lecturer Emily Peters): inclusion-exclusion (chapter 10 of Van Lint and Wilson). Notes (.tex ; .pdf) by Jacob Bower.

Problem Set 1, due Thursday Feb 10.

Lecture 3 (Feb 8): multiplicative functions, Dirichlet series, permutations, Stirling numbers (chapter 13 of Van Lint and Wilson). Notes (.tex ; .pdf) by David Thomas.
Lecture 4 (Feb 10): Stirling numbers continued, linear recurrences. Notes (.tex ; .pdf) by Minseon Shin.

Problem Set 2, due Thursday Feb 17 at the beginning of class.

Lecture 5 (Feb 15): linear recurrences, generating functions (chapter 4 of Stanley; also Concrete Mathematics section 2.6 has more on the analogy between difference calculus and differential calculus). Notes (.tex ; .pdf) by David Witmer.
Lecture 6 (Feb 17): linear recurrences and generating functions continued. Notes (.tex ; .pdf) by Dennis Tseng.

Problem Set 3, due Thursday Feb 24 at the beginning of class.

No class on Tuesday Feb 22 (Monday schedule)
Lecture 7 (Feb 24): partially ordered sets (Stanley 3.1-3.2) Notes (.tex ; .pdf) by Andrew Geng.

Problem Set 4, due Tuesday March 8 at the beginning of class.

Lecture 8 (Mar 1): lattices, Birkhoff's theorem (Stanley 3.3-3.4). Notes (.tex ; .pdf) by Christopher Policastro.
Lecture 9 (Mar 3): chains, linear extensions, incidence algebras (Stanley 3.5-3.6) Notes (.tex ; .pdf) by Damien Jiang.
Lecture 10 (Mar 8): Mobius inversion (Stanley 3.7-3.8) Notes (.tex ; .pdf) by Alex Zhai.
Midterm: Thursday March 10. The material on the midterm will encompass lectures 1-9.

Practice problems for the midterm. If your midterm score was lower than 15, you may hand in one or more of the practice problems PM1, PM7, PM11 by Tuesday March 29. Each problem solved correctly is worth an additional point on the midterm, up to a cap of 15. For example, if your midterm score was 13.5, you could hand in 2 problems to raise it to 15.

Lecture 11 (Mar 15): Mobius inversion continued (Stanley 3.9-3.10). Notes (.tex ; .pdf) by Ben Bond.
Lecture 12 (Mar 17): mu(Pi_n), zeta polynomial, Boolean algebras. Notes (.tex ; .pdf) by Lou Odette.

- Spring Break -

Lecture 13 (Mar 29): combinatorics of finite fields, q-binomial coefficients (Van Lint & Wilson chapter 24). Notes (.tex ; .pdf) by Alex Arkhipov.
Lecture 14 (Mar 31): finite fields continued, hyperplane arrangements Notes (.tex ; .pdf) by Leon Zhou.

Problem Set 5, due Thursday April 7 at the beginning of class.

Lecture 15 (Apr 5): hyperplane arrangements (Stanley 3.11; see also these notes pages 1-5). Notes (.tex ; .pdf) by Jacob Bower.
Lecture 16 (Apr 7): matchings, Hall's marriage theorem (van Lint & Wilson chapter 5). Notes (.tex ; .pdf) by Whan Gheng.

Problem Set 6, due Thursday April 14 at the beginning of class.

Lecture 17 (Apr 12): matchings of planar graphs, Kasteleyn matrix. Notes (.tex ; .pdf) by Santiago Cuellar.
Lecture 18 (Apr 14): Kasteleyn's theorem, domino tilings of an m-by-n rectangle (see chapter 2 of these notes by Richard Kenyon). Notes (.tex ; .pdf) by Taoran Chen.

Problem Set 7, due Thursday April 21 at the beginning of class.

No class on Tuesday Apr 19 (MIT holiday)
Lecture 19 (Apr 21): matrix-tree theorem (Stanley 5.6 in volume 2; see also chapter 9 of Stanley's notes). Notes (.tex ; .pdf) by David Witmer.

Problem Set 8, due Tuesday May 3 at the beginning of class.

Lecture 20 (Apr 26): Eulerian tours (Stanley 5.6 in volume 2; see also chapter 10 of Stanley's notes). Notes (.tex ; .pdf) by Josh Alman.
Lecture 21 (Apr 28): Polya theory of counting (Van Lint & Wilson chapter 37; see also chapter 7 of Stanley's notes). Notes (.tex ; .pdf) by Jacob Bower.
Lecture 22 (May 3): commutative monoids, Smith normal form of an integer matrix. Notes (.tex ; .pdf) by Lou Odette.

In-class final: Thursday May 5. The final will cover material from lectures 10-21.

Practice problems for the final.

Lecture 23 (May 10): abelian sandpile model. Notes (.tex ; .pdf) by David Thomas.
Lecture 24 (May 12): the sandpile group of a graph. Notes (.tex ; .pdf) by Christopher Pollicastro.

Topics:

(subject to change)

Combinatorics and number theory. Possible topics include multiplicative functions, convolution, Dirichlet series, necklace counting; Euclidean algorithm, Stern-Brocot tree, continued fractions and the group SL_2(Z); Sturmian words; counting over finite fields and q-binomial theorem.

Combinatorics and linear algebra. Possible topics include adjacency matrix and Laplacian of a graph, random walks and electrical networks, matrix-tree theorem, counting Eulerian tours; Gessel-Viennot theorem; perfect matchings and Kasteleyn matrix; partially ordered sets, lattices, incidence algebra, Birkhoff's theorem on distributive lattices; Hall's marriage theorem, Dilworth's theorem, max-flow min-cut; linear recurrences and rational generating functions.

Combinatorics and group theory. Possible topics include Polya theory of counting; Cayley graphs; monoids, commutative monoids, minimal ideal; chip-firing; Smith normal form; the sandpile group of a graph and its action on spanning trees.

(Please note that the course catalog description - involving Radon transform, etc. - is out of date and inaccurate!)

Prerequisites:

You should be comfortable with abstract linear algebra (i.e., thinking of a matrix as a function between two vector spaces rather than a block of numbers) and basic group theory. Some familiarity with basic graph theory would be helpful, but is not required. You should know how to write a rigorous proof.

Grading:

Homework (30%): Hand in 30 points worth of problems from the weekly problem sets. Each problem is worth one point (=3 subpoints) unless marked otherwise. Note: once you earn a total of 30 points (=90 subpoints) on problem sets - even if those points are spread out over more than 30 problems - you will get full credit for the homework portion of the grade.

Exams (50%): There will be one midterm (20%, tentative date March 10) and one in-class final (30%, tentative date May 5). There will not be a final during final exam week.

Lecture Notes (20%): Type up notes for one or two lectures using LaTeX. LaTeX is very versatile and widely used for writing technical documents of all kinds. It will serve you well if you go on in math or almost any technical field. The notes are due one week after the lecture and will be posted online as a study aide.

Instructions for notetakers: download the latex template alg-comb-lecture-n.tex and change the "n" in the file name to the number of the lecture you took notes for (the numbers are consecutive integers starting from lecture 1 on Feb 1). When you compile the template in latex, it produces a pdf file that looks like this. To learn more about latex, see this wiki.

If you have questions about the course, or to request a particular topic, please email me.

<-- Back to Lionel Levine's Home Page