Topology in Combinatorics: The Borsuk-Ulam Theorem

Tulasi mohan Molli
Thursday, 12 Mar 2015, 14:00 to 15:00
D-405 (D-Block Seminar Room)
Abstract: We will see an application of topology to prove combinatorial results. The Borsuk-Ulam theorem states that any continuous function f from the surface of the (n+1)-sphere to R^n should have a point x on the sphere such that f(x) = f(-x). For instance when n=2, it implies that if one deflates a football and places it flattened out (arbitrarily) on a table, then there must be two *diametrically opposite* points that land up on top of each other on the table.

Perhaps surprisingly, this theorem can be used to prove the fact that the Kneser-Graph (n,k) has chromatic number exactly n-2k+2 (conjectured by Kneser, proven first by Lovasz in 1978). We will see this and a couple more applications of (variants of) the Borsuk-Ulam theorem in the talk. For some of these results, no purely combinatorial proofs are known.