Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

p Topological Methods in Combinatorics and Geometry - ETH Zürich Spring 2011
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Topological Methods in Combinatorics and Geometry (252-0447-00) FS11

 

Time & Place

Lecture: Tuesdays 11:15-12, HG G 26.3, Thursdays 08:15-10:00, CAB G 59. The lecturer is:
Exercises: Tuesdays 13:15-15:00, CAB G 56. The teaching assistant is:
Anna Gundert, .
 

Contents

 

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

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.

 

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.

    Available online for ETH members.

For general background in (algebraic) topology, we recommend the following books:
  • [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.

Additional references may be pointed out in class.
 

Course Summary and Exercises by Week


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.


Last modified: 31.5.2011 by Anna Gundert.