MT 855: Graduate Combinatorics

Spring 2018

Time: T/Th 9:30-10:50
Location: Maloney 560
Professor: Josh Greene
Office: Maloney 527

Course description: This course will be a panorama of topics in combinatorics, some classical, some very recent, and all fascinating. It is targeted at advanced undergraduate students and graduate students, with a view towards Boston College graduate students writing theses in (algebraic) geometry, topology, and number theory. Very frequently, combinatorial problems surface in different areas, and my hope, in part, is to help you spot them lurking beneath the surface and to train your instincts for addressing them. Furthermore, I hope to emphasize connections between combinatorics and different areas of greater local interest.

I envision the following breakdown of the material:

* classical combinatorics (Ramsey theory, extremal graph theory)
* probabilistic methods (graphs of large girth and chromatic number)
* topological methods (Kneser's conjecture, curves on surfaces)
* algebraic / spectral methods (intersections of set systems, eigenvalues and expansion)
* algebraic geometry / polynomial methods (combinatorial Nullstellensatz, finite field Kakeya, bounds on capsets)
* Guth and Katz's recent work on the Erdos distinct distance problem, which beautifully synthesizes all of the above.

Lecture 1. Course overview.

Lecture 2. Extremal graph theory, part 1. Basic definitions. Mantel's theorem. Turan's theorem. The statement of Erdos-Stone-Simonivits's theorem.

Lecture 3. Extremal graph theory, part 2. The Zarankiewicz problem. Reiman's construction: the incidence graph of a finite plane. Kovari-Sos-Turan's theorem. Brown's construction. Application to combinatorial geometry: the unit distance problem in R^2.

Lecture 4. Ramsey theory, part 1. The party problem. Bounding the classical diagonal Ramsey numbers. Proof of existence of multi-color hypergraph Ramsey numbers. Schur's theorem and how not to prove Fermat's Last Theorem.

Lecture 5. Ramsey theory, part 2. van der Waerden's theorem and the color-focusing proof. The Hales-Jewett theorem. Gallai's theorem.

Lecture 6. The probabilistic method, part 1. Erdos's bound on Ramsey numbers. Szele's theorem on directed Hamiltonian paths.

Lecture 7. The probabilistic method, part 2. Alterations. Ramsey numbers once more. The lower bound for the Zarankiewicz problem.

Lecture 8. The probabilistic method, part 3. Graphs of large girth and chromatic number.

Lecture 9. Graph drawing and the probabilistic method. Planarity and the crossing number lemma.

Lecture 10. Topological methods, part 1. Ghostbusters, equipartitioning points, the Ham Sandwich theorem, and the Borsuk-Ulam theorem.

Lecture 11. Topological methods, part 2. The Lyusternik-Schinerlmann-Borsuk theorem, Borsuk's graphs, Kneser's graphs, and Lovasz's theorem.

Lecture 12. Topological methods, part 3. Necklace splitting. The beginning of Lovasz's proof of Kneser's conjecture.

Lecture 13. Topological methods, part 4. Conclusion of Lovasz's proof of Kneser's conjecture.

Lecture 14. Linear algebra methods, sneak preview; Topological designs, part 1. Oddtown. Disjoint curves on a surface; curves on a surface meeting once in pairs.

Lecture 15. Topological designs, part 2. Curves meeting once in pairs, continued. 1-systems of arcs and curves. Constructions.

Lectures 16 and 17. Topological designs, part 3. Przytycki's theorem on 1-systems of arcs.

Lecture 18. Topological designs, part 4. Bounding the size of a 1-system of curves.

Lecture 19. Classical and Linear algebra methods, part 1. Sperner's theorem. Re-proof of the Oddtown theorem.

Lecture 20. Linear algebra methods, part 2. Fisher's inequality. (mod p) town.

Lecture 21. Linear algebra methods, part 3. The Ray-Chaudhuri-Wilson theorem.

Lecture 22. Linear algebra methods, part 4. Kahn and Kalai's disproof of Borsuk's conjecture. Introduction to the SET problem and the Ellenberg-Gijswijt theorem.

Lecture 23. Linear algebra methods, part 5. Slice rank and the Ellenberg-Gijswijt SET theorem, after Tao.

Lecture 24. News Flash: the chromatic number of the plane is at least 5. The unit distance graph. The Hadwiger-Nelson problem and de Grey's result. The Erdos-de Bruijn theorem and a cautionary example. Coloring the unit distance graph in Euclidean space.

Lecture 25. New Flash, part 2, and the Polynomial Method, part 1. Description of de Grey's construction. Introduction to the finite field Nikodym theorem.

Lecture 26. The Polynomial Method, part 2. Dvir's solution to the finite field Nikodym problem.

Lecture 27. The Polynomial Method, part 3. The finite field Kakeya problem. The joints problem.

Problem Sets:

PS1, PS2, PS3, PS4, PS5, PS6, PS7, PS8, PS9