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

Termín

Cvièení 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 a koná se ve støedu od 14:00 v uèebnì S1.

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 a 2014 è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í).
• Poslední dvì pøedná¹ky jsou upravené podle èlánku: L. Lovász, A homology theory for spanning tress of a graph, Acta Mathematica Hungarica, 241-251, 1977.

Probraná látka

• 27. 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, oblouková souvislost. 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.
• 6. 3. (MB) 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. Borsukova--Ulamova vìta, ¹est ekvivalentních verzí znìní a dùkaz v¹ech ekvivalencí.
• 13. 3. (MB) Dùkaz Kneserovy domnìnky. Doµnikovova vìta a dva její dùkazy.
• 20. 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.
• 27. 3. (MB) Vìta o sendvièi pro bodové mno¾iny a pro bodové mno¾iny v obecné poloze. Znìní ekvipartitních vìt. Znìní center transversal theorem. 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 dùkaz, ¾e implikuje vìtu o spravedlivém dìlení náhrdelníku.
• 3. 4. (MT) Homologický stupeò zobrazení, vlastnosti stupnì. Poèítání stupnì simpliciálního zobrazení pøes poèet kladných a záporných vzorù simplexu. Dvì verze Tuckerova lemma. Dùkaz ekvivalence Tuckerova lemmatu a Borsuk-Ulamovy vìty (BU2b). Pomocné tvrzení pro dùkaz Tuckerova lemmatu (zatím jen znìní).
• 10. 4. (MT) Dùkaz Tuckerova lemmatu z pomocného tvrzení a dùkaz pomocného tvrzeni. Barevná Tverbergova vìta: Pøipomenutí Radonovy a Tverbergovy vìty; znìní barevné Tverbergovy vìty; znìní Blagojeviæ-Matschke-Zieglerovy vìty v slab¹í a silnìj¹í verzi. K dùkazu - zatím jen zapoèata my¹lenka dùkazu.
• 17. 4. (MT) Dùkaz Blagojeviæ-Matschke-Zieglerovy vìty (nìkteré technické kroky vynechány): konstrukce pomocného komplexu K; Sarkaria-Onnova transformace a lemma pøevádìjící Tverbergùv bod nìjakého dìlení na simplex procházející poèátkem; stupeò dìlení vycházející ze S.-O. transformace, konfigurace bez Tverbergova r-dìlení musí mít nulový stupeò, ale kdy¾ r je prvoèíslo, tak je stupeò nenulový.
• 15. 5. (MT) Gyõry-Lovászova vìta - znìní. Arobrescence a komplexy arborescencí. Varianta pro orientované grafy (implikuje variantu pro neorientované grafy). Vìta o homologické souvislosti komplexu arborescencí. Orientovaný Gyõry-Lovász pomocí vìty o homologické souvislosti (zaèátek dùkazu zatím).
• 22. 5. (MT) Dokonèení dùkazu z minula modulo cvièení o selektorech. My¹lenky z dùkazu vìty o homologické souvislosti komplexu arborescencí (poøádnì udìláno pro k=2, pùlka dùkazu pro k=3). [Úplný dùkaz lze najít v èlánku od Lovásze zmínìného v literatuøe.]