MT 855: Graduate Combinatorics
Time: T/Th 9:30-10:50
Location: Maloney 560
Professor: Josh Greene
Office: Maloney 527
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.
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.
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.
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.
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.
Topological methods, part 3.
The beginning of Lovasz's proof of Kneser's conjecture.
Topological methods, part 4.
Conclusion of Lovasz's proof of Kneser's conjecture.
Linear algebra methods, sneak preview; Topological designs, part 1.
Disjoint curves on a surface; curves on a surface meeting once in pairs.
Topological designs, part 2.
Curves meeting once in pairs, continued.
1-systems of arcs and curves.
Lectures 16 and 17.
Topological designs, part 3.
Przytycki's theorem on 1-systems of arcs.
Topological designs, part 4.
Bounding the size of a 1-system of curves.
Classical and Linear algebra methods, part 1.
Re-proof of the Oddtown theorem.
Linear algebra methods, part 2.
(mod p) town.
Linear algebra methods, part 3.
The Ray-Chaudhuri-Wilson theorem.
Linear algebra methods, part 4.
Kahn and Kalai's disproof of Borsuk's conjecture.
Introduction to the SET problem and the Ellenberg-Gijswijt theorem.
Linear algebra methods, part 5.
Slice rank and the Ellenberg-Gijswijt SET theorem, after Tao.
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.
New Flash, part 2, and the Polynomial Method, part 1.
Description of de Grey's construction.
Introduction to the finite field Nikodym theorem.
The Polynomial Method, part 2.
Dvir's solution to the finite field Nikodym problem.
The Polynomial Method, part 3.
The finite field Kakeya problem.
The joints problem.
PS1, PS2, PS3, PS4, PS5, PS6, PS7, PS8, PS9