Department of Computer Science | Institute of Theoretical Computer Science | CADMO
Prof. Emo Welzl and Prof. Bernd Gärtner
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.
Graded Homework: Three times in the semester (roughly every three weeks), we will hand out a specially marked exercise which we ask to be solved and handed in two weeks later. The solutions to these exercises will be graded, and these grades will count towards the final grade. You are welcome to discuss the exercises with your colleagues, but we ask that all students write down their solutions individually and in their own words.
Sets of exercises will also be handed out in other weeks. Students are recommended to solve the exercises and hand in writeups which will be corrected, but not graded. As an incentive to also work on these exercises, it is possible to gain up to 1/3 of the points for the exercise grade by presenting solutions (of the non-special assignments) in class.
The final exams will take place on June 14th and 15th. The total final grade will be a combination of the exercise grade and the exam grade. Exercises account for 40%, the exam for 60% of the final grade. Passing grades for both parts are required.
Note that credit points (KE) for PhD students will be given according to the regulations of their respective departments. In particular, for D-INFK PhD students the rule for obtaining credits will be the same as for masters students, i.e. they will not receive credit points for simply sitting in the course or only successfully solving the special exercises. For PhD students of other departments other rules may apply.
For the most part, the course will follow the book
[Mat] J. Matoušek. Using the Borsuk-Ulam Theorem. Springer-Verlag, 2003.
Available online for ETH members.
For general background in (algebraic) topology, we recommend the following books:Additional references may be pointed out in class.
[Hat] A. Hatcher. Algebraic Topology. Cambridge University Press, 2001.
A 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.
[Pra] V.V. Prasolov. Elements of combinatorial and differential topology. AMS, 2006, and Elements of homology theory. AMS, 2007.
A very intuitive and geometric introduction to algebraic and differential topology, with many examples of concrete use. The second book is essentially a continuation of the first one.
[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. AMS, 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. Vorlesungsskript.
Lecture notes for a basic topology course taught at ETH Zürich.
[Zie] G. M. Ziegler. Topology. Lecture Notes.
Lecture notes for a basic topology course taught at TU Berlin.
Date | Content | Exercises | References | ||
22.2.2011 | Motivation: the chromatic number of Kneser graphs. | ||||
24.2.2011 | Topological basics: topological spaces, subspaces, continuous maps, homeomorphisms, connectedness, path connectedness, Haussdorff spaces, compactness. | Problem Set 1 | [Mat, Section 1.1], [Jän, Chapter 1], [Pra, Basic Definitions], [Zie, Chapter 1] |
||
1.3.2011 | More on compactness; definitions of deformation retract, homotopy of maps, homotopy equivalence of spaces. | Problem Set 2 + Solution of Question 3 |
[Jän, Sections 1.8, 5.1-2], [Zie, Chapter 1], [Mat, Section 1.2], [Hat, Chapter 0] |
||
3.3.2011 | Product topology; repetition: deformation retract, homotopy of maps, homotopy equivalence of spaces; simplices and geometric simplicial complexes; triangulations. | [Jän, Section 1.3], [Mat, Section 1.2-1.4] |
|||
8.3.2011 | Bottom-vertex triangulation of a convex polytope; more about simplicial complexes: abstract simplicial complexes and geometric realizations, simplicial maps. | Problem Set 3 Here and here you can find pictures of triangulated tori. |
[Mat, Section 1.5] | ||
10.3.2011 | Affine extensions of simplicial maps; simplicial approximation theorem. | [Mat, Section 1.5], [Pra, Section 2.4] |
|||
15.3.2011 | Every simplicial complex can be realized in dimension 2d+1; Examples of simplicial complexes; The Borsuk-Ulam theorem in various equivalent forms. | First Graded Exercise | [Mat, Section 1.6,2.1] | ||
17.3.2011 | Proof of the equivalence of the various versions of the Borsuk-Ulam theorem; back to simplicial complexes: order complexes of posets and face posets of simplicial complexes, barycentric subdivision; The Ham-Sandwich theorem, version for measures. Here is a short summary of the basic measure-theoretic facts that we used in the proof of the Ham-Sandwich theorem (including a proof of continuity of the relevant function and the proof of the theorem itself.) |
[Mat, Section 2.1, 1.7, 3.1] | |||
22.3.2011 | Discrete Ham-Sandwich theorem, general position version. | [Mat, Section 3.1] | |||
24.3.2011 | Examples of equipartition theorems (without proofs); impossibility of equipartitioning into 32 pieces in R^5 by 5 hyperplanes. The necklace theorem for 2 thieves. Review of Kneser graphs; the Lovasz-Kneser theorem; Greene's proof. The m-colorability defect of a set system; Dolnikov-Kriz theorem. Gale's lemma; Barany's proof of the Lovasz-Kneser theorem. | [Mat, Chapter 3] | |||
29.3.2011 | Proof of Gale's lemma; Schrijver graphs; the lower bound for their chromatic number. Tucker's lemma; proof of the equivalence with the Borsuk-Ulam theorem. | Problem Set 4 | [Mat, Section 3.5, Section 2.3] | ||
31.3.2011 | Preparations for proof of Tucker's lemma: Preliminaries for Z_2-homology (chains, boundary map), definition pseudomanifold, degree of simplicial map between pseudomanifolds. Bing's house, collapsibility, remarks on collapsibility vs. contractibility. | [Mat, Section 2.4] | |||
5.4.2011 | Proof of Tucker's lemma continued. | Problem Set 5 | [Mat, Section 2.4] | ||
7.4.2011 | Proof of Tucker's lemma finished. A quick introduction into Z_2-homology. | [Mat, Section 2.4] | |||
12.4.2011 | Formulation Szemeredi-Trotter theorem; polynomial Ham-Sandwich theorem. | ||||
14.4.2011 | Proof of the Szemeredi-Trotter theorem. Z_2-space, Z_2-action, Z_2-map, simplicial Z_2-complex. Example of a simplicial Z_2-action on the simplicial complex sd(2^{[n]}\[n]). | Second Graded Exercise | [Mat, Section 5.2] | ||
19.4.2011 | Introduction to fair division. Brouwer's fixed point theorem and Sperner's Lemma. Here are notes from this lecture. |
Problem Set 6 Question 2 is the existence statement of Thm 1 in this paper. |
|||
21.4.2011 | Two proofs of Sperner's Lemma. Envy-free division with Sperner's Lemma. Here are notes from this lecture. |
||||
3.5.2011 | Deleted product of a topological space as an example of a free Z_2-space. Remark: G-spaces, G-maps (for finite groups G). The construction of the box complex B(G) for a graph G. | [Mat, Sections 5.4, 5.9, 6.1] | |||
5.5.2011 | Graph homomorphisms induce Z_2-maps of the box complexes. Definitions of Z_2-index and Z_2-coindex of a Z_2-space. The box complex of a complete graph is a sphere. Theorem: the chromatic number of any graph G is at least ind(B(G))+2. Definition of a k-connected topological space. Theorem: The n-dimensional sphere is (n-1)-connected but not n-connected. | [Mat, Sections 4.3, 5.3, 5.9] | |||
10.5.2011 | 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. Remarks on computability of n-connectivity. Remark: Hurewicz's theorem. | Third Graded Exercise with bonus questions! |
[Mat, Section 5.3] | ||
12.5.2011 | Remark: Nerve theorem. The neighborhood complex N(G) of a graph G; fact (without proof): it is homotopy equivalent to B(G). The generalized Mycielski construction (no proofs given). Embeddability of simplicial complexes in R^d. Examples: graph planarity, the Van Kampen-Flores complexes, topological Radon theorem. Definition: the deleted product of a simplicial complex. Theorem: if ind(deleted product of K) >= d, then K doesn't embed in R^d (use the Gauss map). Remark: this simple theorem is a powerful tool (e.g. because of the Haefliger-Weber theorem). | [Mat, Sections 4.4, 5.1, 5.4, 5.9] | |||
17.5.2011 | Join (combinatorial and geometric interpretation). | [Mat, Section 4.2] | |||
19.5.2011 | Examples of joins. Deleted join of a simplicial complex. Theorem: If ind(deleted join of K)>d, then K doesn't embed in R^d. Deleted join of a simplex is a sphere. Theorem: ind(deleted join of K) >= |V(K)|-1-c, where c is the chromatic number of the Kneser graph of the system of all inclusion-minimal non-simplices of K. | [Mat, Section 5.5, 5.7, 5.8] | |||
24.5.2011 | Proof of last theorem continued: Lower bound for ind(deleted join of K). Lemma: ind(K*L) is at most ind(K)+ind(L)+1. | [Mat, Section 5.8] | |||
26.5.2011 | A brief excursion to homotopy groups. Outlook on other results in topological combinatorics: Smallest number of Tverberg partitions, Colored Tverberg Theorem. | ||||
31.5.2011 | Outlook on other results in topological combinatorics: Configuration space/test map scheme. | Here are lecture notes for all of Prof. Matousek's lectures. | |||