This is a 28-lecture course with each lecture lasting about 30 minutes.
This course will cover a miscellaneous collection of topics in combinatorics and closely related fields. What the topics have in common is that they all involve proofs that at one time surprised experts by their simplicity. Sometimes these were the first proofs of long-standing open problems, and sometimes they were new proofs of results that had previously been established by much longer arguments. Several of these arguments use ideas and techniques that have gone on to be used by many other people.
Another theme of the course is the sheer diversity of methods that are used in combinatorics. We shall see uses of probability, linear algebra, linear analysis, topology, entropy, multivariate polynomials, tensor rank, concentration of measure, and more. (There will also be one or two arguments that are completely elementary.)
- Welcome
- Averaging and double counting
- Intersecting families
- Sperner’s theorem
- Crossing numbers and point-line incidences
- Bounds for factorials and binomial coefficients
- Families of well separated sets
- Sets of vectors with no acute angles, and Hadamard matrices
- Solymosi’s bound for the sum-product problem
- Variants of the Borsuk-Ulam theorem
- Two applications of the Borsuk-Ulam theorem
- The Marcus-Tardos theorem
- Entropy axioms and some simple consequences
- Further properties of entropy
- Using entropy to count paths of length 3
- The formula for entropy
- An entropy proof of Brégman’s theorem
- Subadditivity of entropy and Shearer’s lemma
- Two applications of Shearer’s lemma
- Dvir’s solution to the finite-field Kakeya problem
- Alon’s Combinatorial Nullstellensatz and two applications
- The slice rank of a diagonal 3-tensor
- An exponentially small upper bound for the cap-set problem
- Huang’s solution to the sensitivity conjecture
- Dimension arguments and sets with only two distances
- Intersections with restricted parity
- The Frankl-Wilson theorem on restricted intersection sizes
- Sets without orthogonal pairs, and Borsuk’s conjecture
These videos were produced by Tim Gowers and form his Part III course at the University of Cambridge. Printed notes for this course are available here.
