“The Discrete Charms of TOPOLOGY”
MURAD
OZAYDIN
(
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 :
Time : 15.40
Place: Mathematics Seminar Room SA141
Tea
will be served before the seminar.