The previous talk in the series is here. The next talk in the series is here.
Here I show how to use the Borsuk-Ulam theorem to find a graph with no short odd cycles but with very high chromatic number, and then to give a solution to the Kneser conjecture. The latter concerns the chromatic number of the Kneser graph, which has as its vertex set the set of all subsets of {1,2,…,2n+k} of size n, with two sets joined if they are disjoint. The conjecture is that the chromatic number is k+2. A simple example shows that a proper colouring with k+2 colours exists. László Lovász famously proved the conjecture using the Borsuk-Ulam theorem, which was the first application of topological methods in combinatorics. Soon afterwards, his proof was considerably simplified by Imre Bárány, and a lot later it was simplified even further by Joshua Greene, who was a student at the time. Here I present Greene’s proof. We start by finding a triangle-free graph with chromatic number at least 2020, then look at Greene’s proof of the Kneser conjecture.
This video was produced by Tim Gowers as part of his Part III course at the University of Cambridge. Printed notes for this course are available here.