Math 128, Current Problems in Combinatorics (Spring 2009)

Textbook

There is no official textbook for this course. The textbooks from which the lectures will be planned, which may be helpful as resources, are:

We will also refer to whenever possible.

Scheduled Lectures

The course meets Tuesday and Thursday from 10:00 – 11:50 in Kemeny 201. (We will take a 10 minute break roughly in the middle of each lecture.)

Note that the "Thursday Lunch Expedition" immediately follows the Thursday lectures, and that this is in turn followed by the Combinatorics Seminar.

The x-hour is Wednesday 3:00 – 3:50, but its use is not anticipated.

Instructor

Vince Vatter
Office: 314 Kemeny Hall
Office hours: by appointment
Phone: 646-3507
Blitzmail: vincent.vatter (preferred)

Grades

Students will be assessed based on their written homework. There will be no in-class exams.

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 Date Topics
1 Tuesday 3/31 Overview of combinatorics, also counting
Supplemental reading: Enumerative and algebraic combinatorics, What is an answer?
2 Thursday 4/2 Derangements, permanents, involutions, and the Erdos-Szekeres Theorem
3 Tuesday 4/7 Inclusion-exclusion, the Bell numbers, the Stirling numbers
4 Thursday 4/9 Hall's marriage theorem and the number of Latin squares of order n
5 Tuesday 4/14 The proof of Evans' Conjecture: If at most n-1 cells of an n by n array are filled (with no repetitions in the rows or columns), then the array can be extended to a Latin square of order n.

Homework #1 assigned
6 Thursday 4/16 Posets, and the theorems of Dilworth, Mirsky, and Sperner
7 Tuesday 4/21 Downsets, especially in \mathbb{N}^m
8 Thursday 4/23 The Fundamental Theorem of Finite Distributive Lattices

Homework #2 assigned
9 Tuesday 4/28 Mobius inversion
10 Thursday 4/30 Dimension Theory for posets
11 Tuesday 5/5 Rational generating functions

Homework #3 assigned
12 Thursday 5/7 Algebraic and D-finite generating functions
13 Tuesday 5/12 Formal languages
14 Thursday 5/14 Permutation patterns
15 Tuesday 5/19 Permutation patterns

Homework #4 assigned
16 Thursday 5/21 Guest lecture by Prof. Peter Winkler on the probabilistic method
17 Tuesday 5/26 The Combinatorial Nullstellensatz
18 Thursday 5/28 The Combinatorial Nullstellensatz