Using the Borsuk-Ulam theorem

Lectures on topological methods in combinatorics and geometry

Jiri Matousek

with the collaboration of Anders Bjorner and Guenter M. Ziegler

Springer (Heidelberg), April 2003; publisher's page.

errata

NEW: Corrected and updated second printing, fall 2007

New material: a brief introduction to the cohomological index and to Hom complexes of graphs, plus a number of smaller updates.

From the preface

There are several combinatorial and geometric results whose proofs (the first proofs and often the only known proofs) involve a surprising application of algebraic topology. Lovasz's striking proof of Kneser's conjecture from 1978 was among the first and most prominent examples, dealing with a problem about finite sets with no apparent relation to topology.

During the last two decades, topological methods in combinatorics have become more elaborate. On the one hand, quite advanced parts of algebraic topology have been successfully applied. On the other hand, many of the earlier results can now be proved using only fairly elementary topological notions and tools, and while the first topological proofs, like that of Lovasz, are masterpieces of imagination and involve clever problem-specific constructions, reasonably general recipes exist at present.

This book aims at making some of the elementary topological methods more easily accessible to non-specialists in topology. It covers a number of substantial results proved by topological methods, and at the same time, it introduces the required material from algebraic topology. Background in undergraduate mathematics is assumed, as well as a certain mathematical maturity, but no prior knowledge of algebraic topology.

Table of contents, with links to sample sections

Preliminaries

1 Simplicial Complexes
1.1 Topological spaces
1.2 Homotopy equivalence and homotopy
1.3 Geometric simplicial complexes
1.4 Triangulations
1.5 Abstract simplicial complexes
1.6 Dimension of geometric realizations
1.7 Simplicial complexes and posets

2 The Borsuk-Ulam Theorem
2.1 The Borsuk-Ulam theorem in various guises
2.2 A geometric proof
2.3 A discrete version: Tucker's lemma
2.4 Another proof of Tucker's lemma

3 Direct Applications of Borsuk--Ulam
3.1 The ham sandwich theorem
3.2 On multicolored partitions and necklaces
3.3 Kneser's conjecture
3.4 More general Kneser graphs: Dolnikov's theorem
3.5 Gale's lemma and Schrijver's theorem

4 A Topological Interlude
4.1 Quotient spaces
4.2 Joins (and products)
4.3 k-connectedness
4.4 Recipes for showing k-connectedness
4.5 Cell complexes

5 Z_2-Maps and Nonembeddability
5.1 Nonembeddability theorems: An introduction
5.2 Z_2-spaces and Z_2-maps
5.3 The Z_2-index
5.4 Deleted products good ...
5.5 ... deleted joins better
5.6 Bier spheres and the Van Kampen-Flores theorem
5.7 Sarkaria's inequality
5.8 Nonembeddability and Kneser colorings
5.9 A general lower bound for the chromatic number

6 Multiple Points of Coincidence
6.1 G-spaces
6.2 E_nG spaces and the G-index
6.3 Deleted joins and deleted products
6.4 Necklace for many thieves
6.5 The topological Tverberg theorem
6.6 Many Tverberg partitions
6.7 Z_p-index, Kneser colorings, and p-fold points
6.8 The colored Tverberg theorem

A Quick Summary

Hints to Selected Exercises

Bibliography

Index

Comments are greatly appreciated (mistakes, missing references, passages that are confusing or difficult to understand...). Please mail your comments to "matousek" at the address "kam.mff.cuni.cz".