**Lectures:** Tuesday and Thursday 10-11:30

**Instructor:** Thomas Lam, 2834 East Hall,
tfylam@umich.edu

**Office Hours:** Tuesday and Thursday 2-3:30pm

No office hours on October 4 or October 6.

On October 13, I have to attend a thesis defense at 2. However, I should be back in my office some time after 3pm.

**Prerequisites:**

You have to be comfortable with reading and writing proofs. Some experience with abstract algebra, such as group theory or proof-based linear algebra
is assumed. Past experience with combinatorics is also helpful.

**Grading:**
There will be problem sets every one or two weeks. There will be no final exam.

The midterm will be on Thursday October 20 during class time.

Grades will be calculated from: Midterm (25%) and Problem Sets (75%).

**Midterm:**
The midterm covers material in Chapters 3,4,5,33.
The midterm is "one open book". You can bring your textbook, or a single book consisting of your notes.
The midterm will be 80 minutes.

**Textbook (Required):**
A course in combinatorics, J. H. van Lint and R. M. Wilson, 2nd edition.

**Homework policy:**
You are allowed to work with other students on the problem sets, but you must include the names of those you worked with when you hand in your homework. You are not allowed to post homework problems on question websites such as mathoverflow or stackexchange. If you use a solution you find in a book, online, or elsewhere, you must acknowledge the source.

**Syllabus (subject to change):**

Extremal Graph Theory and Combinatorics:

Turan's theorem, Ramsey's theorem, Brooks' theorem, chromatic number and polynomial, planar graphs and graphs on surfaces, five-color theorem, Van der Waerden's theorem

Geometric Combinatorics:

projective and combinatorial geometries, matroids, hyperplane arrangements, characteristic polynomials, geometric lattices, polytopes

**List of lectures:**

- Sep 6: Turan's theorem
- Sep 8: More proofs of Turan's theorem
- Sep 13: chromatic number, Brook's theorem
- Sep 15: Ramsey's theorem
- Sep 20: Lower bound for Ramsey number (Theorem 3.7), Van der Waerden's theorem, Erdos Szekeres theorem
- Sep 22: graphs with no 4-cycle, graphs with high girth and high chromatic number
- Sep 27: planar graphs, Euler's formula, five color theorem (Chapter 33)
- Sep 29: chromatic polynomials, deletion and contraction, acyclic orientations
- Oct 4: Hall's marriage theorem
- Oct 6: No Lecture
- Oct 11: Systems of distinct representatives
- Oct 13: Latin squares
- Oct 18: Fall Break
- Oct 20: Midterm
- Oct 25: Latin squares
- Oct 27: Dinitz conjecture
- Nov 1: Projective planes
- Nov 3: Projective planes
- Nov 8: Orthogonal Latin squares and projective planes
- Nov 10: Combinatorial geometries
- Nov 15: Posets and lattices
- Nov 17: Geometric lattices
- Nov 22: Bases, independent sets, and rank
- Nov 24: Thanksgiving
- Nov 29: Counting flats, etc.
- Dec 1: Hyperplane arrangements
- Dec 6: Characteristic polynomials
- Dec 8: No lecture
- Dec 13: Graphical arrangements