Math 68, Algebraic Combinatorics (Fall 2009)

Textbook

We will be using A Walk Through Combinatorics by Miklos Bona, supplemented by handouts as needed.

Scheduled Lectures

The course meets Mondays, Wednesdays, and Fridays from 1:45 – 2:50 in Haldeman 028.

Instructor

Vince Vatter
Office: 314 Kemeny Hall
Office hours: Monday 12:00 – 1:00, Tuesday 1:00 – 3:00, and by appointment
Phone: 646-3507
Blitzmail: vincent.vatter (preferred)

Grades

The grades are based on weekly homework (assigned on Fridays, due on Wednesdays), an in-class midterm, and a take-home final. All three components count equally.

The Honor Principle

On homework, collaboration is permitted and encouraged — a discussion of the general idea of the problem(s) with others is desirable. However, each student is expected to complete his or her assignments individually and independently.

Very Rough Draft of Tentative Schedule

Lecture(s) Dates Topics Chapter
1 Wednesday 9/23 Binomial coefficients, unimodality, log-concavity 4
2 Friday 9/25 Compositions
Homework #1 assigned (due on Wednesday) 		5
3 Monday 9/28 Set partitions 5
4 Wednesday 9/30 Integer partitions 5
5 Friday 10/2 Permutations and their cycles
Homework #2 assigned (due on Wednesday) 		6
6 Monday 10/5 Permutations and their cycles 6
7 Wednesday 10/7 Posets: Dilworth's Theorem and Mirsky's Theorem 16
8 Friday 10/9 The incidence algebra and Mobius inversion
Homework #3 assigned (due on Wednesday) 		16
9 Monday 10/12 Common Mobius functions 16
10 Wednesday 10/14 Mobius functions of lattices; in particular the lattice of set partitions 16
11 Friday 10/16 Sperner's theorem on antichains in the Boolean lattice and the Littlewood-Offord problem
Homework #4 assigned (due on Wednesday) 		16
12 Monday 10/19 Generating functions 8
13 Wednesday 10/21 Rational generating functions 8
14 Friday 10/23 Algebraic generating functions, and in particular, the Catalan numbers
Homework #5 assigned (due on Wednesday) 		8
15 Monday 10/26 Bootstrap percolation, the separable permutations, and the Schröder numbers 8
16 Wednesday 10/28 Exponential generating functions (note: not covered on midterm) 8
Wednesday 10/28
6:00–8:00pm		 Midterm in Kemeny 004
Friday 10/30 Class cancelled (scheduled)
17 Monday 11/2 Graphs and maximal independent sets 9
Wednesday 11/4 Class cancelled (due to flu)
18 Friday 11/6 Graphs and maximal independent sets, continued
Homework #6 assigned (due on Wednesday) 		9
19 Monday 11/9 The Max-Flow Min-Cut Theorem n/a
20 Wednesday 11/11 Baranyai's Theorem n/a
21 Thursday 11/12
x-hour		 The Matrix-Tree Theorem 10
22 Friday 11/13 The Matrix-Tree Theorem, continued; note that there is a much prettier proof of Cayley's formula
Homework #7 assigned (due on Wednesday) 		10
23 Monday 11/16 Groups, Permutation Groups, and Automorphism Groups n/a
24 Wednesday 11/18 Enumeration under group action (Póyla's Theorem) n/a
25 Friday 11/20 Enumeration under group action (Póyla's Theorem), continued n/a
26 Monday 11/23
Thanksgiving recess begins Tuesday		 Combinatorial algorithms; for an entertainingly bad sorting algorithm, see here. 17
27 Monday 11/30 Basics of computational complexity n/a
28 Wednesday 12/2 P vs. NP n/a
Friday 12/11 Final exam is due