Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry

Front Cover
Springer Science & Business Media, Jun 4, 2003 - Computers - 196 pages
0 Reviews

A number of important results in combinatorics, discrete geometry, and theoretical computer science have been proved using algebraic topology. While the results are quite famous, their proofs are not so widely understood. They are scattered in research papers or outlined in surveys, and they often use topological notions not commonly known among combinatorialists or computer scientists.

This book is the first textbook treatment of a significant part of such results. It focuses on so-called equivariant methods, based on the Borsuk-Ulam theorem and its generalizations. The topological tools are intentionally kept on a very elementary level (for example, homology theory and homotopy groups are completely avoided). No prior knowledge of algebraic topology is assumed, only a background in undergraduate mathematics, and the required topological notions and results are gradually explained.

At the same time, many substantial combinatorial results are covered, sometimes with some of the most important results, such as Kneser's conjecture, showing them from various points of view.

The history of the presented material, references, related results, and more advanced methods are surveyed in separate subsections. The text is accompanied by numerous exercises, of varying difficulty. Many of the exercises actually outline additional results that did not fit in the main text. The book is richly illustrated, and it has a detailed index and an extensive bibliography.

This text started with a one-semester graduate course the author taught in fall 1993 in Prague. The transcripts of the lectures by the participants served as a basis of the first version. Some years later, a course partially based on that text was taught by Günter M. Ziegler in Berlin. The book is based on a thoroughly rewritten version prepared during a pre-doctoral course the author taught at the ETH Zurich in fall 2001.

Most of the material was covered in the course: Chapter 1 was assigned as an introductory reading text, and the other chapters were presented in approximately 30 hours of teaching (by 45 minutes), with some omissions throughout and with only a sketchy presentation of the last chapter.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Simplicial Complexes
1
12 Homotopy Equivalence and Homotopy
4
13 Geometric Simplicial Complexes
7
14 Triangulations
10
15 Abstract Simplicial Complexes
13
16 Dimension of Geometric Realizations
16
17 Simplicial Complexes and Posets
17
The BorsukUlam Theorem
21
An Introduction
88
52 Z₂Spaces and Z₂Maps
92
53 The Z₂Index
95
54 Deleted Products Good
108
55 Deleted Joins Better
112
56 Bier Spheres and the Van KampenFlores Theorem
116
57 Sarkarias Inequality
121
58 Nonembeddability and Kneser Colorings
124

21 The BorsukUlam Theorem in Various Guises
22
22 A Geometric Proof
30
Tuckers Lemma
35
24 Another Proof of Tuckers Lemma
42
Direct Applications of BorsukUlam
47
32 On Multicolored Partitions and Necklaces
53
33 Knesers Conjecture
57
Dolnikovs Theorem
61
35 Gales Lemma and Schrijvers Theorem
64
A Topological Interlude
69
42 Joins and Products
73
43 kConnectedness
78
44 Recipes for Showing kConnectedness
80
45 Cell Complexes
82
Z₂Maps and Nonembeddability
87
59 A General Lower Bound for the Chromatic Number
128
Multiple Points of Coincidence
144
62 EnG Spaces and the GIndex
149
63 Deleted Joins and Deleted Products
157
64 The Topological Tverberg Theorem
161
65 Many Tverberg Partitions
165
66 Necklace for Many Thieves
167
67 ZpIndex Kneser Colorings and pFold Points
170
68 The Colored Tverberg Theorem
174
A Quick Summary
179
Hints to Selected Exercises
184
References
187
Index
203
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »

About the author (2003)

Jiri Matousek is Professor of Computer Science at Charles University in Prague.

Bibliographic information