Lecture: Topological methods in Combinatorics (M. Tancer)

General information

This year, the lecture is merged with Mathematics++. All the information (for the merged lecture) will appear on this webpage.

Schedule and tutorials

Lecture is scheduled to the room S11 (Malá Strana) on Tuesdays, 12:20.
Tutorials are taught by Tomá¹ Hons and Petr Chmel. They are scheduled to the room S6 (Malá Strana) or sometimes to the corridor S321 if the room is not avalable on Tuesdays, 15:40. They will appear irregularly; see the schedule on the tutorial webpage.

Content of the lecture

This year (2024), the lecture will be a combination of lectures "Topological Methods in Combinatorics" and "Mathematics++".

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.
The content of Mathematics++ varies with the period of three years. This year the topic would be topology which is the reason for merging. In more detail, for Mathematics++, the aim would be to provide more detailed introduction to topology intended for students of computer science including the basics of algebraic topology but also focusing on possible applications.

In the merged lecture we intend to cover the most of the traditional content of Topological Methods in Combinatorics focusing mainly on the applications. However, we also save some time for a brief explaination of a few important notions from algebraic topology (fundamental group, homology groups) with possible applications.

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 2021.

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/ .

Topics Covered

Lecture	Contents	Literature
Lecture 1, Feb 22	Motivation: Kneser graphs, Colorful Tverberg theorem. Basic notions from topology: Topological space (examples: standard topology on $\mathbb R^d$, Sierpinski space); open and closed sets; subspace; Hausdorff spaces; continuous maps; homeomorphism; the closure, the boundary and the interior of a set in a topological space; compact topological spaces. Examples: $\mathbb R$ is not compact, $[0,1]$ is compact (with a proof). A closed subset of a compact space is compact. A compact subset of a Hausdorff space is closed.	[KMS, Chap. 6.1, 6.2 and 6.3] (But these chapters contain more than what have been said during the lecture).
Lecture 2, Feb 29	Compact sets, continued: An image of a compact set is compact. Basis of a topology. Product of topological spaces. Tychonoff's theorem (without proof). Characterization of compact subsets of $\mathbb R^d$. A continuous map attains a minimum on a compact set. Connected topological space and a component of connectedness. Homotopy equivalence (started): Derfomation rectract; homotopy of maps; nullhomotopic maps.	Compactness [KMS, Chap. 6.3]; connectedness [KMS, Chap. 6.2] or wikipedia (for components); homotopy equivalence [M, Chap. 1.2] or [KMS, Chap. 6.4].
Lecture 3, Mar 7	Homotopy equivalence of topological spaces. (Remark on equivalent characterization using deformation retracts.) Simplicial complexes: Geometric simplicial complexes. Polyhedron (underlying space) of a geometric simplicial complex; dimension. Triangulation of a topological space. Examples how to get $S^{n-1}$ and torus. Abstract simplicial complexes. Relation between the abstract and the geometric simplicial complexes. A simplicial map.	Literature: [M, Chap. 1.2--1.5] (or [KMS, Chap 6.4 and 6.7] but explained slightly differently)
Lecture 4, Mar 14	Simplicial map induces a continuous map on polyhedra. Proposition on properties of the induced map (without proof). Barycentric subdivision. Borsuk-Ulam theorem: six equivalent formulations. Proof of the equivialence of the formulations (so far (BU1a) $\Leftrightarrow$ (BU1b) $\Leftrightarrow$ (BU2a) and (BU2a) $\Rightarrow$ (BU2b)).	Literature: [M, Chap, 1.5--2.1] (only parts of the chapters).
Lecture 5, Mar 21	Finishing the proof of the equivalence from last time. One more equivalent formulation (LS-co), proof will be a homework. Applications: Kneser graphs. Kneser conjecture/Lovász theorem. Greene's proof of the theorem. Coloring hypergraphs and colorability defect. Doµnikov's theorem. (Proof will appear on the next lecture.)	Literature: [M, Chap 2.1, 3.3, 3.4]
Lecture 6, Mar 28	Proof of Doµnikov's theorem. Schrijver's graphs. Schrijver's theorem (on chromatic number of Schrijver's graphs). Moment curve and its basic properties. Gale's lemma. Proof of Schrijver's theorem via Gale's lemma and then a proof of Gale's lemma.	Literature: [M, Chap 3.4, 3.5, 1.6 (for the moment curve)]
Lecture 7, Apr 4	Ham sandwich theorem for measures. Explanation of the statement including a definition of finite Borel measure. Proof (modulo Dominated convergence theorem; few details skipped here and there). Ham sandwich theorem for point sets. (Few details in the proof skipped again.)	Literature: [M, Chap 3.1]
Lecture 8, Apr 11	Ham sandwich theorem for point sets in general position. Akiyama-Alon theorem on partitioning into rainbow $d$-tuples. Necklace theorem. Hobby-Rice theorem. (Sketched a proof via ham-sandwich; more complete proof directly from Borsuk-Ulam.) Remarks on equipartition theorems. Tucker's lemma.	Literature: [M, Chap 3.1, 3.2, 2.3]
Lecture 9, Apr 14	An equivalent version of Tucker's lemma (via simplicial maps). Equivalence of the Borsuk-Ulam theorem and Tucker's lemma. A proof of Tucker's lemma via `happy simplices'. The proof works only for special triangulations but this is enough to deduce the Borsuk-Ulam theorem which in turn implies Tucker's lemma in full generality.	Literature: [M, Chap 2.3]