**Lectures:** Tuesday and Thursday 10-11:30
1437 Mason Hall

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

**Office Hours:** Tuesday and Thursday 2:40-4pm, starting September 12

**Prerequisites:**

The most important prerequisite is mathematical maturity.You have to be comfortable with reading and writing proofs. In particular, proofs by contradiction and proofs by induction will be common and used without further explanation. 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 roughly every one or two weeks. There will be one midterm. There will be no final exam.

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

**Midterm:**
The midterm will be on Thursday October 19 during class time. 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.
The midterm will cover material from Chapters 3,4,5,33 of the textbook.

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

**Homework policy:**
Homework is due at the start of class. Homeworks handed in after the lecture has started are considered **late**, and penalized. Homeworks handed in later than the end of class **are not accepted**. There are no makeups for late homework; the lowest homework score will be dropped in the final calculation.

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.

**Disabilities:**
The University of Michigan is committed to providing equal opportunity for participation in all programs, services and activities. Request for accommodations by persons with disabilities may be made by contacting Services for Students with Disabilities (SSD) Office located at G664 Haven Hall. The SSD phone number is 734-763-3000 and website is here. Once your eligibility for an accomodation has been determined you will be issued with a verified individual services accommodation (VISA) form. Please present this form to me at the beginning of the term, or at least two weeks prior to the need for the accommodation.

**Syllabus (subject to change):**

Extremal Graph Theory and Combinatorics:

Turan's theorem, Ramsey's 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

See last year's course for a list of topics that will be similar to this year's.

**List of lectures:**

- Sep 5: Turan's theorem
- Sep 7: More proofs of Turan's theorem
- Sep 12: Brook's theorem
- Sep 14: Ramsey's theorem
- Sep 19: Applications of Ramsey's theorem, Van der Waerden's theorem
- Sep 21: Avoiding cycles in graphs
- Sep 26: Planar graphs, Euler's formula, chromatic polynomial
- Sep 28: Acyclic orientations, Five-color theorem
- Oct 3: Five-color theorem, chromatic number of the plane
- Oct 5: Hall's marriage theorem
- Oct 10: Konig's theorem, Birkhoff's theorem
- Oct 12: Latin squares
- Oct 17: Fall break
- Oct 19: Midterm Exam
- Oct 24: Dinitz conjecture
- Oct 26: Finite projective planes
- Oct 31: Projective planes from fields
- Nov 2: Projective planes continued
- Nov 7: Combinatorial geometries
- Nov 9: Geometric lattices
- Nov 14: Bases in combinatorial geometries
- Nov 16: Hyperplane arrangements, Mobius function
- Nov 21: Restriction-contraction, number of regions
- Nov 28: Graphical arrangements
- Dec 1: Broken circuit theorem
- Dec 5: Polytopes
- Dec 12: Guest lecture by Gabe Frieden