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

Støeda od 9:00 v posluchárnì S1.

Cvièení následuje ve støedu od 10:40 v S1. Bude probíhat pøedev¹ím metodou samostatné práce posluchaèù (øe¹ení domácích úkolù). Cvièení povedou Martin Balko a Martin Tancer.

Anotace

Jedním z dùle¾itých dùkazových prostøedkù v diskrétní matematice je aplikace vìt z algebraicke 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), Borsuk-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 roku 2010 èi podobné pøedná¹ky na ETH v Curychu. Nicménì obsah bude tentokrát ponìkud obmìnìn.

Literatura

• J. Matousek: Using the Borsuk-Ulam theorem, Springer 2003. Na teto strance jsou i nektere kapitoly v elektronicke podobe.
• Na webu je k dispozici velmi pekny uvod do algebraicke topologie od Allena Hatchera, viz
   http://www.math.cornell.edu/~hatcher/ .
• Asi nejctivejsi solidni uvod do topologie, co zname, jsou knihy V.V. Prasolova Elements of combinatorial and differential topology, AMS, 2006, a Elements of homology theory, AMS, 2007 (druha je pokracovanim prvni).

Probraná látka

• 25. 2. Úvod. Kneserùv graf KG(n,k), chromatické èíslo Kneserova grafu (jen znìní odhadu). Radonovo lemma, Tverbergova vìta a barevná Tverbergova domnìnka/vìta (u v¹eho jen znìní). 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, oblouková souvislost.
• 4. 3. Silný deformaèní retrakt, 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. Simpliciální zobrazení a izomorfismus simpliciálních komplexù.
• 11. 3. Spojité zobrazení mezi nosnými prostory simpliciálních komplexù odvozené od simpliciálního zobrazení. Prosté simpliciální zobrazení (resp. simpliciální izomrfismus) indukují prosté spojité zobrazení (resp. homeomorfismus). Barycentrické podrozdìlení abstraktního simpliciálního komplexu. Borsuk-Ulamova vìta - ¹est ekvivalentních verzí znìní. Zatím dokázaná ekvivalence prvních pìti znìní.
• 25. 3. Ekvivalence uzavøené a otevøené verze Ljusternik - ©nireµmanovy vìty. Dùkaz Kneserovy domnìnky. Doµnikovova vìta a její dùkaz. Zmínka o Schrijverových grafech.
• 1. 4. Galeho lemma. Bárányùv dùkaz Kneserovy domnìnky pomocí Galeho lemmatu. Momentová køivka a její vlastnosti ohlednì prùnikù s nadrovinami. Dùkaz Galeho lemmatu. Dùkaz odhadu chromatického èísla Scrijverových grafù. Ham-Sandwich theorem, mìrová verze, znìní + zaèátek dùkazu (zbývá dokázat spojitost urèité funkce definované v dùkazu).
• 8. 4. Dokonèení dùkazu z minula. Ham-Sandwich pro bodové mno¾iny a pro bodové mno¾iny v obecné poloze. Ekvipartitní vìty. Akiyama-Alonova vìta o dìlení na duhové simplexy. Vìta o spravedlivém dìlení náhrdelníku. Neformální povídání o fundamentální grupì a vy¹¹ích homotopických grupách.
• 9. 4. Úvod do simpliciální homologie nad celými èísly. Orientované simplexy. Øetìzce a øetìzcové grupy. Hranièní operátor. Grupy cyklù a hranic. Homologické grupy jako faktorové grupy "cykly podle hranic". Pøíklad výpoètu. Homologické grupy d-simplexu.
• 15. 4. Homologie (triangulace) d-sféry (s odkazem na to, ¾e homotopicky ekvivalentní prostory mají izomorfní homologické grupy); v dimenzi d spoèítaná poøádnìji; fundamentální tøída. Náznak dùkazu, ¾e R^m není homeomorfní s Rⁿ pro m, n rùzná. Simpliciální zobrazení mezi dvìma komplexy indukuje homomorfismus f_# mezi øetìzcovými grupami, a tento homomorfismus zobrazení komutuje s hranièním operátorem. Jako dùsledek, f_# dále indukuje homomorfismus f_* mezi odpovídajícími homologickými grupami. Funktorialita f_*. Dùkaz Brouwerovy vìty o pevném bodì, modulo to, ¾e se musí pou¾ít singulární homologie, o které jsme nemluvili. Homologický stupeò zobrazení, jeho vlastnosti (mj. Hopfova vìta). Výpoèet stupnì pomocí vzorù simplexu (zatím jen znìní).
• 22. 4. Dùkaz lemmatu o poèítání stupnì. Tuckerovo lemma. Reformulace pomocí simpliciálních zobrazení do køí¾ového mnohostìnu. Ekvivalence Tuckerova lemmatu s Borsuk-Ulamovou vìtou (staèí dokonce dokázat slab¹í verzi lemmatu pro odvození Borsuk-Ulamovy vìty). Pomocné tvrzení: zobrazení roz¹íøitelné na kouli má nulový stupeò, zatímco antipodální zobrazení má lichý stupeò (jen pro speciální triangulace). Odvození Tuckerova lemmatu z pomocného tvrzení a dùkaz pomocného tvrzení.
• 23. 4. Pøipomenutí barevné Tverbergovy vìty. Verze barevné Tverbergovy vìty od Blagojeviæe, Matschkeho a Zieglera. Duhová dìlení odpovídají maximálním simplexùm v jistém "spojení" ¹achovnicových komplexù (komplex K z my¹lenky dùkazu). Sarkaria-Onnova transformace.