Topological methods in Combinatorics, Lent 2012

When:

Tuesdays, Thursdays at noon

Where:

MR5, CMS

What:

Topology is an infrequent but a powerful visitor to the world of combinatorics. In this course we shall see applications to graph theory, combinatorial geometry, and complexity theory. From topology we will cover simplicial complexes, Borsuk–Ulam theorem, ham-sandwich theorem (with cheese), nerve theorem, Z₂-index. Combinatorial applications will include necklace splittings, chromatic numbers of Kneser graphs, topological Radon's theorem, evasiveness.

Resources:

We will closely follow Using Borsuk–Ulam by Jiří Matoušek. For evasiveness we shall use the notes by László Lovász. Some of the applications will come from the original papers. We do not assume any background in algebraic topology, but acquaintance with the basics will be very helpful. A good introductory book is Homology theory by James Vick. Another good book is by Allen Hatcher.

Lectures:

Note that there will be no lectures on 28th of February, and on 1st of March due to my absence.

• January 19: Introduction.
• January 24: Simplicial complexes.
• January 26: Borsuk–Ulam theorem in different guises.
• January 31: Tucker's lemma. Basic notions of simplicial homology. Half of Tucker's lemma.
• February 2: Another half of Tucker's lemma. Chromatic number of Kneser graphs.
• February 7: Brouwer's fixed point theorem. Ham sandwich theorem. Notes on the ham sandwich theorem.
• February 9: Necklace splitting. Determinancy of the Hex.
• February 14: Graph non-embeddability. G-spaces. Joins, deleted joins.
• February 16: Z₂-index, topological Radon theorem, G-homotopy.
• February 21: Simplicial homology. Lefschetz–Hopf formula. Lefschetz fixed point theorem.
• February 25: Connectivity. E_nG spaces. Borsuk–Ulam theorem for E_nG spaces. G-index. Notes on wedges and joins.
• February 28: No lecture.
• March 1: No lecture.
• March 6: Universality of E_nG spaces. Dold's theorem. Sarkaria's inequality. Van Kampen–Flores theorem.
• March 8: Theorem of Makeev. Evasiveness.
• March 13: Collapsibility. Z_n-invariant properties are evasive.