21-801: Algebraic Methods in Combinatorics

Here is some preliminary information on the course.

Summary

I will present various "non-combinatorial" techniques that have proved useful in combinatorics (algebraic / topological / analytical / etc methods). A part of the course (2-4 weeks) will be seminar-like: we will have student presentations covering parts of the book "Using Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry" by Jiri Matousek.

List of Topics

Here is a preliminary list of topics I'll try to cover or touch upon:

Lagrangian of hypergraphs
higher incidence matrices
intersection theorems
chromatic number of R^n
Borsuk's conjecture, including

Kahn-Kalai construction

Hinrich's counterexamples from the Leech lattice

Shannon & Sperner capacities
Alon's Combinatorial Nullstellensatz
Wilson's constructions in design theory
eigenvalues and expanders,including

zig-zag product of Reingold, Vadham and Wigderson

Gurvits' proof of van der Waerden's permanent conjecture using hyperbolic polynomials
graphons and Razborov's flag algebras
Borsuk-Ulam Theorem

Prerequisite

21-701

Previous Lecture Notes

My lecture notes from 2001 can be found here. Some parts of them will be used in the current course.

Course Handouts So Far

Click here.

-OP