Special Topics in Computer Science (CS492)

Introduction to topological methods in combinatorics and geometry

Spring Semester 2008

The course offers an introduction in solving problems in combinatorics and discrete geometry by topological methods with special emphasis on the Borsuk-Ulam theorem and its generalizations. Some main results to be covered are the solution of Kneser's conjecture, and the van Kampen-Flores theorem. The aim is to make some of the elementary topological methods more easily accessible to non-specialists in topology. Background in undergraduate mathematics is assumed, as well as a certain mathematical maturity, but no prior knowledge of algebraic topology.


Andreas Holmsen and Otfried Cheong. Office: E3-1 3434, Phone: 3542.


The class meets Monday, Wednesday, and Friday from 14:00 to 14:50 in room 2443 in the Computer Science Building (E3-1). Lectures are given in English.

Grading policy

Students will be graded based on homeworks and a quiz.


We will use the following textbook:


Here is a rough list of what we will cover in each week of the semester.

Week 1 Introduction
Week 2 Topological spaces
Week 3 Simplicial complexes
Week 4 Abstract simplicial complexes
Week 5 The Borsuk-Ulam theorem
Week 6 Ham-Sandwich theorem
Week 7 Kneser's Conjecture
Week 8 Midterm exam week
Week 9 Dolnikov's Theorem
Week 10 Gale's Lemma
Week 11 Nonembeddability theorems
Week 12 Deleted products and joins
Week 13 The Van Kampen-Flores Theorem
Week 14 G-Spaces
Week 15 The Topological Tverberg Theorem
Week 16 Final Exam week

Course progress

The material covered in the lectures so far:

02-11 Introduction
02-13 Simplicial complexes
02-15 Simplicial mappings
02-18 Chain mappings, odd and even maps
02-20 Borsuk-Ulam in two dimensions
02-22 Sperner's Lemma, general Borsuk-Ulam
02-25 Brouwer's fixpoint theorem from Sperner's lemma
02-27 Ham-Sandwich cut, Necklace
02-29 No class
03-03 Necklace theorem, Kneser's theorem
03-05 Partitioning a measure with two lines, review
03-07 Colored caratheorody lecture notes
03-10 Quotient space
03-12 Join
03-14 Partitioning a measure by 3 coincident lines
03-17 Z2-space and Z2-maps
03-19 The Z2-index
03-21 No class
03-24 The Z2-index (cont.)
03-26 Z2-index and non-embeddability
03-28 No class
Midterm week
04-07 Bier-spheres de Longueville's proof
04-09 Holiday
04-11 Sarkaria's inequality
04-14 Sarkaria's coloring theorem
04-16 Four points form a rectangle
04-18 Homework discussion
04-21 Box-complex, introduction to G-spaces
04-28 No class
04-30 No class
05-02 No class
05-05 Holiday
05-12 Holiday
05-14 Quiz


There will be a few homework assignments in this course. You will have about one to two weeks to complete an assignment. Homeworks must be submitted on paper and must be handed in at the beginning of class.

Bulletin board

We have a bulletin board for announcements and discussions. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Otfried Cheong