---

Time & Place

Lecture: Thursdays 10:15-12:00, CAB H 52. The lecturers are:
Exercises: Thursdays 13:15-14:00, CAB G 57. The teaching assistant is:

Contents

• Course Description
• Grades, Exercises, Exam
• References and Additional Reading
• Course Summary and Exercises by Week

Course Description

A number of results in combinatorics and (discrete) geometry have striking proofs that use methods from algebraic topology, e.g., Lovász' proof of Kneser's conjecture or the Zivaljevic-Vrecica proof of the colorful version of Tverberg's theorem. In some cases, alternative, non-topological proofs have later been found (as in the case of Kneser's conjecture, even though the combinatorial proofs are still motivated by the underlying topological intuition), while in other cases, the topological methods are still the only ones available.

In this course, we cover some of the basic topological notions and results (simplicial complexes, Borsuk-Ulam theorem and its generalizations etc.) and complete proofs of several combinatorial and geometric applications. The topological notions and results are kept on an elementary level. In particular, knowledge of basic algebraic topology, like homotopy or homology theory, is (encouraged but) not required.

Procedures, exercises, exam

Every Thursday, a new set of exercises will be handed out, which we ask be solved and handed in the following week. You may discuss the problems with other students, but we ask that all students write down their solutions individually and in their own words. The solutions will be graded and generally handed back to the students one week later. You need to achieve 80% or more of the possible points to get a grade of 6.0 for the exercises; 40% of the possible points are required for a passing grade (4.0).

The final exam will take place in the last week of the semester. The total final grade will be a combination of your exercise grade and your exam grade, each counting 50%. Passing grades for both parts are required.

For PhD students there are special rules concerning credit points (KE) for the course. If your supervisor agrees, you may simply sit in on the course and obtain 2 KE. If you successfully solving the exercises, you get additional 2 KE. In order to obtain the last remaining 1 KE, you have to take and pass the final exam.

References and Additional Reading

For the most part, the course will follow the book

• [Mat] J. Matoušek. Using the Borsuk-Ulam Theorem. Springer-Verlag, 2003.

For general background in (algebraic) topology, we recommend the following books:

• [Hat] A. Hatcher: Algebraic Topology. Cambridge University Press, 2001.

  A fairly recent and very readable (not to be confused with easy!) introduction to algebraic topology. The author maintains a complete and up-to-date free electronic version for download on his homepage.

• [Mun] J. R. Munkres. Elements of Algebraic Topology. Addison-Wesley, Reading, MA, 1984.

  This is another one of the standard introductions to algebraic topology. One thing that distinguishes it from most of the other algebraic topology textbooks and makes it particularly useful for combinatorial applications is its emphasis on simplicial complexes and simplicial (co)homology.

• [Vas] V.A. Vassiliev. Introduction to Topology. American Mathematical Society, 2001.

  Despite the title this is not a textbook in the classical sense from which one can learn the subject in detail, but rather a bird's-eye view of the fundamentals of algebraic and differential topology. One should not expect to understand everything on first reading, and there are few full and detailed proofs or even completely formal definitions that start from scratch, but if one is willing to go with the flow, the book gives a very interesting perspective on things and manages to illustrate and explain a lot in just 150 pages.

• [Jän] K. Jänich. Topology. Springer Verlag, New York, 2007.

  A short introduction to basic topology (mostly point-set topology, even though some more algebraic aspects, such as the fundamental group, are also touched upon). The author takes great pains to motivate and explain the intuition behind the definitions and proofs. An electronic version of the latest German edition (K. Jänich. Topologie. 8. Auflage) is available (from within the ethz.ch domain) through the ETH library, see the NEBIS catalog.

• [Pink] R. Pink. Topologie. Vorlesungs-Skript.

  Lecture notes for a basic topology course taught at ETH Zürich.

Additional references will be pointed out in class.

Course Summary and Exercises by Week

Date	Content	Exercises	References
21.2.2008	Motivating problems (the chromatic number of Kneser graphs; ham-sandwich cuts). Topological basics: topological spaces and continuous maps; compactness; homeomorphism.	Problem Set 1	[Mat, Section 1.1], [Jän, Chapter 1], [Pink, Chapters 1-6,9]
28.2.2008	Haussdorff spaces; product topology; homotopy of maps, homotopy equivalence of spaces, and retracts; simplices and geometric simplicial complexes.	Problem Set 2 +	[Mat, Sections 1.2-1.7], [Hat, Chapter 0], [Pink, Chapters 17 & 15]
6.3.2008	More about simplicial complexes: barycentric coordinates, simplicial maps and affine extensions; abstract simplicial complexes and geometric realizations.	Problem Set 3 +	[Mat, Sections 1.2-1.7]
13.3.2008	Still more about simplicial complexes: links and stars of faces; joins of complexes; stellar subdivisions and barycentric subdivisions; order complexes of posets and face posets of complexes.	Problem Set 4 +	[Mat, Sections 1.7,4.2], [Mun, Sections 2 and 62]
20.3.2008	The Borsuk-Ulam theorem in various equivalent forms.	Problem Set 5 + Optional Easter Problem Set	[Mat, Sections 2.1,2.2]
3.4.2008	The Ham-Sandwich theorem, continuous and discrete. Here is a short summary of the basic measure-theoretic facts that we used in the proof of the theorem (including a proof of continuity of the relevant function and the proof of the theorem itself, hopefully more concise and clearer than the discussion in class.)	Problem Set 6
10.4.2008	Discrete Ham-Sandwich for general position. Examples of equipartition theorems (without proofs); impossibility of equipartitioning into 32 pieces in R^5 by 5 hyperplanes. The Akiyama-Alon theorem. The necklace theorem for 2 thieves. Review of Kneser graphs. The Lovasz-Kneser theorem. Greene's proof.	Problem Set 7
17.4.2008	The m-colorability defect of a set system. Dolnikov-Kriz theorem. Barany's proof of the Lovasz-Kneser theorem; Gale's lemma. Schrijver graphs. The lower bound for their chromatic number. Z_2-space, Z_2-action, Z_2-map. Example of a simplicial Z_2-action on the simplicial complex sd(2^{[n]}\[n]).	Problem Set 8 (The due date was shifted.)
24.4.2008	Notion: simplicial Z_2-complex. Remark: G-spaces, G-maps (for finite groups G). The construction of the box complex B(G) for a graph G; graph homomorphism induces a Z_2-map of the box complexes. A geometric proof of the Borsuk-Ulam theorem (to be finished next time).	Problem Set 9
8.5.2008	Finished the proof of the Borsuk-Ulam theorem (writeup here). Z_2-index and Z_2-coindex of a Z_2-space; simple properties; k-connected topological space.	Problem Set 10
15.5.2008	The n-dimensional sphere is (n-1)-connected but not n-connected (proof only sketched). If X is an n-connected Z_2-space, then ind(X) is at least n+1. If K is an n-dimensional free simplicial Z_2-complex, then ind(K) is at most n. Theorem: the chromatic number of any graph G is at least ind(B(G))+2. Neighborhood complex N(G); fact: it is homotopy equivalent to B(G). Theorem of Lovasz: If N(G) is k-connected, then the chromatic number of G is at least k+3. Nonembeddability problems (introduction). Definition: the deleted product of a simplicial complex.	Problem Set 11 (Please, follow the due date! I leave 30th May.)
22.5.2008	Support supp(x) of a point in a polyhedron. Theorem: If the deleted product of a finite simplicial complex K has Z_2-index at least d, then the polyhedron of K doesn't embed in R^d; what is more, any continuous map of K into R^d identifies two points with disjoint supports. Main trick in the proof: (x,y)\mapsto (f(x)-f(y))/|f(x)-f(y)|. Remark: this simple theorem is a powerful tool (e.g. because of the Haefliger-Weber theorem). Join K*L of simplicial complexes. Geometric representation (using two skew subspaces). Consequence: join depends only on the polyhedra. Points of the polyhedron of K*L written as formal linear combinations tx\oplus (1-t)f(y). Examples (S^k*S^l = S^{k+l+1}). Join of Z_2-spaces, ind(K*L) is at most ind(K)+ind(L)+1. Deleted join. Theorem: If ind(deleted join of K) is at least d+1, then K is not embeddable in R^d (also statement with disjoint supports like for deleted product).

---