Borsuk’s
Theorem, Kneser’s conjecture and Lovasz’s proof:
A survey featuring also
Tucker’s Lemma
and Matousek’s proof.
By Fred Holroyd
The Open University
Abstract:
Borsuk’s Theorem concerns covering a sphere with open sets no two points of which are antipodal. What does this have to do with the chromatic number of Kneser graphs? Until 2003, the proof that the Kneser graph, KG(m,n) has chromatic number m-2n+2 was proved in general only via topology. Is Matousek’s new combinatorial proof really a topological proof in disguise? You are invited to consider the question.
Tuesday, February 15, 2005
At 3:30 in Wallace 430