# Informace k přednášce "Topologické metody v kombinatorice"  (Martin Balko, Martin Tancer, KAM) 2021/2022

EN: Topological methods in combinatorics: The webpade is partially in Czech; however, the important information is also in English. We start on February 25!

## Exams

Agreement on exams is via email. Send a message to Martin Tancer if you want to pass the exam and we will agree on a suitable date for your exam. (At the moment I know that one exam will be on June 3. It is welcome if you want to join for this date but other dates are also possible, of course.)

For certain topics (not many) it will be allowed either to use handwritten notes, or some details can be skipped; see the explanation below. If you are not sure whether you have identified correctly the items in the explanation below, send a query to Martin Tancer with the list of unclear items.

• For homology and the proof of Borsuk-Ulam theorem it is allowed to prepare handwritten notes (written with your own hand) for the following items:
1. f# induces a homomorphism f* of homology groups (as a corollary of commutativity of f# with the boundary homomorphism.)
2. Proof that Tucker lemma (for sufficiently fine triangulations) implies the Borsuk-Ulam theorem.
3. Proof of the auxiliary Lemma (used in the proof of Tucker lemma).

Explanation: You should be able to understand the proofs but we do not want from you to memorize the technical details.

The hand written notes should not contain any further information and they will be used only if you are asked about the corresponding topic during the exam.

• For the colorful Tverberg theorem the target will be to understand the general structure of the proof but several technical details may be skipped. Namely, it is sufficient to know the following items.
1. Two versions of the Blagojević-Matschke-Ziegler theorem (including the necessary definitions for understanding the statements).
2. Construction of K including stating the properties of K
3. Construction of f and the statment of the Sarkaria-Onn lemma. (Proof can be skipped).
4. Definition of a degree of a collection as the degree of F (or f if you like it better).
5. Explaining how properties (i), (ii), (iii) (of the degree of a collection) imply Blagojević-Matschke-Ziegler theorem. (It is not necessary to know how to prove them.)

## General information (in Czech)

#### Termín

Přednáška se koná v pátek od 9:00 v učebně S4, cvičení jsou od 10:40 též v učebně S4. Zde je link na cvičení. Začínáme až 25 února.

Cvičení bude probíhat především metodou samostatné práce posluchačů (řešení domácích úkolů). Cvičení povedou Denys Bulavka a Michael Skotnica.

#### Anotace

Jedním z důležitých důkazových prostředků v diskrétní matematice je aplikace vět z algebraické topologie, zejména různých vět o pevném bodě apod. V přednášce probereme potřebné topologické pojmy a výsledky a dokážeme několik kombinatorických a geometrických výsledků topologickými metodami. Vhodné pro studenty vyšších ročníků matematiky, teoreticky zaměřené informatiky a pro doktorandy. Speciálně pro informatiky může sloužit i jako (náhražkový) úvod do topologie, nesmírně významného odvětví matematiky, s nímž se však v průběhu základního studia běžně vůbec nesetkají.

#### Osnova

Základní pojmy obecné topologie, simpliciální komplexy (pojmy a základní fakta), Borsukova-Ulamova věta, její zobecnění a aplikace, věty o nevnořitelnosti a barevnosti (např. barevnost Kneserových grafů). O probrané látce si můžete udělat představu z obsahu minulého běhu přednášky z let 2010, 2014 a 2018 či podobné přednášky na ETH v Curychu. Nicméně obsah bude tentokrát poněkud obměněn.

### Literatura

• J. Matoušek: Using the Borsuk-Ulam theorem, Springer 2003. Na této stránce jsou i některé kapitoly v elektronické podobě.
• Na webu je k dispozici velmi pěkný úvod do algebraické topologie od Allena Hatchera, viz http://www.math.cornell.edu/~hatcher/ .
• Asi nejčtivější solidní úvod do topologie, co známe, jsou knihy V.V. Prasolova Elements of combinatorial and differential topology, AMS, 2006, a Elements of homology theory, AMS, 2007 (druhá je pokračováním první).

## Contents of the lectures

• 25. 2. (MB) Úvod. Kneserův graf KG(n,k), chromatické číslo Kneserova grafu (jen znění odhadu), věta o sendviči, řezání konvexních těles. Základní definice obecné topologie: topologický prostor, otevřená a uzavřená množina, Hausdorffovy prostory, podprostor, spojité zobrazení, homeomorfismus, uzávěr, vnitřek a hranice, kompaktní množiny, souvislost, křivková souvislost. (Silný) deformační retrakt. Prezentace [PDF].
English: 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].
• 4. 3. (MB) Homotopická zobrazení, homotopie topologických prostorů, kontraktibilní prostor. Geometrický simplicální komplex, nosný prostor (polyédr). Triangulace sféry jako hranice simplexu a hranice křížového mnohostěnu. Abstraktní simpliciální komplex, geometrická realizace abstraktního komplexu. Spojité zobrazení mezi nosnými prostory simpliciálních komplexů odvozené od simpliciálního zobrazení. Prezentace [PDF]. Bohužel se přednášku nepodařilo nahrát.
English: 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. Presentation [PDF]. Unfortunately, the recording of the lecture was not successful.
• 11. 3. (MT) Properties of the mapping derived from the simplicial map between two complexes (proof only sketched). Barycentric subdivisions. Polyhedron of a complex and of its barycentric subdivision are homemorphic (without proof). General definition of a subdivision in a geometric simplicial complex. Borsuk-Ulam theorem: six equivalent statements. So far, the equivalence of the first five has been proved.
• 18. 3. (MB) Důkaz ekvivalence (LS-o) s (LS-c) v Borsukově--Ulamově větě, důkaz Kneserovy domněnky. Doľnikovova věta a její důkaz. Prezentace [PDF], záznam [ZIP].
English Proof of the equivalence (LS-o) with (LS-c) in the Borsuk--Ulam theorem, proof of the Kneser's conjecture, Doľnikov's theorem and its proof. Presentation [PDF], recorded lecture [ZIP].
• 25. 3. (MB) Schrijverovy grafy. Galeho lemma. Momentová křivka a její vlastnosti ohledně průniků s nadrovinami. Důkaz Galeho lemmatu. Důkaz odhadu chromatického čísla Schrijverových grafů. Věta o sendviči, měrová verze. Prezentace [PDF], záznam [ZIP].
English: Schrijver's graphs. Galeho lemma. Moment curve and its properties about intersections with hyperplanes. Proof of Gale's lemma. Proof for the lower bound on the chromatic number of Schrijver's graphs. The Ham sandwich theorem, version for measures. Presentation [PDF], recorded lecture [ZIP].
• 1. 4. (MB) Věta o sendviči pro bodové množiny a pro bodové množiny v obecné poloze. Znění ekvipartitních vět (jen v prezentaci). Akiyama--Alonova věta o dělení na duhové simplexy. Věta o spravedlivém dělení náhrdelníku. Hobbyho--Riceova věta a náznak toho, že implikuje větu o spravedlivém dělení náhrdelníku. Prezentace [PDF], záznam [ZIP].
English: The Ham sandwich theorem for point sets and for point sets in general position. Statements of the theorems about equipartition (only on the slides). Akiyama--Alon theorem about partitioning into rainbow simplices. The Necklace theorem. Hobby--Rice theorem and a sketch of the fact that it implies the Necklace theorem. Presentation [PDF], recorded lecture [ZIP].
• 8. 4. (MT) Motivation for homology: very briefly fundamental group, then addition of cycles, notion of boundaries. Preliminaries for homology: oriented simplices; k-chains; boundary operator including the fact that it is well defined; composition of two boundary operators is zero. Definition of homology: k-cycles, k-boundaries, kth homology group. Small example: the 1-cycles are essentially flows in a graph.
• 22. 4. (MT) Exact computaion of the homology of the boundary of a triangle. Homology of the simplex and of the boundary of the simplex. Top dimension homology of an arbitrary triangulation of the sphere. Functoriality of homology: f# commutes with the boundary operator; induced homomorphism f* on homology; theorem on functoriality. The homological degree of a map (definition only for the moment).
• 29. 4. (MS) Properties of the homological degree and a lemma on its computation. Tucker lemma and its reformulation via crosspolytope. Tucker lemma is equivalent to the Borsuk-Ulam theorem. Due to the proof of this equivalence, it is sufficient to prove Tucker's lemma for fine enough triangulation.
• 6. 5. (MT) An auxiliary lemma for the proof of Tucker lemma. (Proof that Tucker's lemma follows from the auxiliary lemma and then the proof of the auxiliary lemma.) Introduction to the colored Tverberg theorem including stating Blagojević-Matschke-Ziegler theorem.
• 13. 5. (MT) Another version of Blagojević-Matschke-Ziegler theorem that implies the earlier one. Main ideas of the proof: we build a complex K and a map f. Then K is an orientable gallery connected pseudomanifold which allows to compute the degree of f. Degree of a collection is defined as a degree of f. Three properties (i), (ii), (iii) imply Blagojević-Matschke-Ziegler theorem. More detials for the proof: Construction of K, Sarkaria-Onn transform (started).
• 20. 5. (MT) Sarkaria-Onn lemma. Construction of f. Verifying properties (i), (ii), (iii). (Some steps for (ii) and (iii) only sketched.)