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

Exams

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

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