School of Technology and Computer Science Seminars
Topology in Combinatorics: The Borsuk-Ulam Theorem
by Mr. Rakesh Venkat (School of Technology and Computer Science, TIFR)
Thursday, March 12, 2015
from
to
(Asia/Kolkata)
at D-405 (D-Block Seminar Room)
at D-405 (D-Block Seminar Room)
Description |
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. |