“The Discrete Charms of TOPOLOGY”









Abstract: There are theorems in discrete mathematics with continuous proofs (sometimes with no other known proofs). Some examples are Lovasz's proof of the Kneser Conjecture (on the chromatic number of certain graphs) and the prime power case of the Evasiveness Conjecture. These are consequences of classical theorems of topology such as the Borsuk-Ulam theorem or fixed point theorems of Lefschetz and P. A. Smith. Another (which will be discussed in detail) is Alon & West's solution of the Necklace Splitting problem: To split an open necklace with N types of gems (with an even number of identical gems of each type) fairly between two thieves N cuts suffice (no matter how many gems there are of each type or how they are arranged on the necklace). Note that if we have the "silly necklace", i.e., all the rubies together, then all the emeralds, etc., we do need N cuts. field.






Date : September 30, 2009 (Wednesday)

Time : 15.40

Place: Mathematics Seminar Room SA141



Tea will be served before the seminar.