Lecture: Topological methods in Combinatorics (M. Balko and M. Tancer)

General information

Schedule and tutorials

Lecture is scheduled to the room S7 (Malá Strana) on Mondays, 12:20.
Tutorials are taught by Todor Antic. They are scheduled to the room S6 (Malá Strana) on Mondays 14:00. See the tutorial webpage.

Content of the lecture

The traditional content of Topological Methods in Combinatorics is a brief introduction to topology (intended for students of computer science who possibly does not meet it in other lectures) and then the main content are applications of topology in combinatorics, discrete mathematics or combinatorial geometry. (This should be new both for students of mathematics or computer science). One example of such an application is that the chromatic number of so-called Kneser graphs can be determined via topological tools.

Previous lectures

If you are interested in the content of the lectures Topological Methods in Combinatorics of Mathematics++ in previous years, you can check: Topological methods in 2022, or Mathematics++ in 2024.

Language

The language of the lecture will be Czech or English depending on the audience. (If there is an attendee who does not understand Czech, the lecture will be in English).

Literature (may be extended during the semester)

[M] J. Matou¹ek: Using the Borsuk-Ulam theorem, Springer 2003.
[H] Algebraic Topology by A. Hatcher: http://www.math.cornell.edu/~hatcher/ .
[Mu] J. R. Munkres: Elements of Algebraic Topology
Research articles:
[BMZ] P. Blagojeviæ, B. Matschke, G. M. Ziegler: Optimal bounds for the colored Tverberg problem
[MTW] J. Matou¹ek, M. Tancer, U. Wagner: A geometric proof of the colored Tverberg theorem

Topics Covered

Lecture	Contents	Literature
Lecture 1, 23.2. (MB)	Introduction. Kneseger's graph KG(n,k), chromatic number of Kneser's graphs (just statement), the Ham Sandwich Theorem. fair cutting of convex bodies. Basic definitions from general topology: topological space, open set and closed set, Hausdorff space, subspace, continous mapping, homeomorphism, closure, interior and boundary, compact sets, connectivity, path-connectivity. (Strong) deformation retract. Presentation [PDF],notes (in Czech) [PDF].	[M, Chap. 1].
Lecture 2, 2. 3. (MB)	Homotopic mappings, homotopy of topological spaces, contractible space. Geometric simplicial complex, carrier (polyhedron). Triangulation of the sphere as a boundary of a simplex and as a boundary of a crosspolytope. Abstract simplicial complex, geometric representations of an abstract simplicial complex. Continuous mapping between polyhedra of simplicial complexes derived from a simplicial mapping, statement of the Simplicial approximation theorem barycentric subdivisions. Presentation [PDF], notes (in Czech) [PDF].	[M, Chap. 1].
Lecture 3, 9. 3. (MB)	The Borsuk-Ulam Theorem, proof of all the equivalences. Proof of Brouwer's Fixed Point Theorem using the Borsuk-Ulam Theorem. Presentation [PDF], notes [PDF].	[M, Chap. 1].
Lecture 4, 30. 3. (MT)	Applications of the Borsuk-Ulam theorem: Kneser graphs and the Lovász--Kneser theorem. Coloring hypergraphs and Doµnikov's theorem. Schrijver's graphs and Schrijver's theorem. Proof of Schrijver's theorem will appear at the next lecture. So far we stated Gale's lemma and sketched its proof.	[M, 3.3, 3.4, 3.5].
Lecture 5, 13. 4. (MT)	Proof of Schirjver's theorem. Ham sandwich theorem: Motivation; a version for finite Borel measures; a version for finite point sets.	[M, 3.5, 3.1]
Lecture 6, 20. 4. (MT)	Ham sandwich theorem: An improved version for point sets in general position. Remarks on equipartition theorems. Applications of Ham sandwich: Akiyama-Alon theorem; necklace theorem. Hobby--Rice theorem (a proof expected at the tutorials). Tucker's lemma: Motivation, two equivalent formulations. Proof that Tucker's lemma is equivalent to the Borsuk--Ulam theorem (BU2b).	[M, 3.1, 3.2, 2.3]
Lecture 7, 27. 4. (MT)	Proof of Tucker's lemma (via happy simplices). The proof is for special triangulations but by earlier considerations, it implies (BU2b) and Tucker's lemma in general. Motivation for the topological Radon and Tverberg theorems. (The standard statements, affine versions and topological versions---so far only statements.)	[M, 2.3, 5.1, 6.5]