Informace k prednasce "Topologicke metody v kombinatorice" 
(Jiri Matousek, Martin Tancer, KAM) 2010/2011

Úterky od 9:00 v posluchárnì S1.

Anotace

Jednim z dulezitych dukazovych prostredku v diskretni matematice je aplikace vet z algebraicke topologie, zejmena ruznych vet o pevnem bode a pod. V prednasce probereme potrebne topologicke pojmy a vysledky a dokazeme nekolik kombinatorickych a geometrickych vysledku topologickymi metodami. Vhodne pro studenty vyssich rocniku matematiky, teoreticky zamerene informatiky a pro doktorandy. Specialne pro informatiky muze slouzit i jako (nahrazkovy) uvod do topologie, nesmirne vyznamneho odvetvi matematiky, s nimz se vsak v prubehu zakladniho studia bezne vubec nesetkaji.

Osnova

Zakladni pojmy obecne topologie, simplicialni komplexy (pojmy a zakladni fakta), Borsuk-Ulamova veta, jeji zobecneni a aplikace, vety o nevnoritelnosti a barevnosti (napr. barevnost Kneserovych grafu) Cviceni vede Marek Krcal a bude zejmena formou samostatne prace posluchacu (reseni domacich ukolu), viz stranku cviceni O probrané látce si mù¾ete udìlat pøedstavu z obsahu minulého bìhu pøedná¹ky z roku 2007 è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).

Probrana latka

• 11.10. Úvod. Barevnost a zlomková barevnost grafu. Kneserùv graf KG(n,k), Kneserova domnìnka (znìní). Lemma o hodnì pokrytém bodu (znìní). Základní definice obecné topologie: topologický prostor, otevøená a uzavøená mno¾ina, podprostor, spojité zobrazení, homeomorfismus. Souvislost. Oblouková souvislost.

• 18.10. Uzávìr, hranice, vnitøek. T_2 prostory. Kompaktní mno¾iny (vztah s uzavøenými mno¾inami, obraz kompaktní mno¾iny, kompaktní mno¾iny v R^d, spojitá funkce na kompaktní mno¾inì nabývá extrémù). Báze topologie, souèinová topologie. Tichonovova vìta (znìní).

• 25.10. Silná deformaèní retrakce. Homotopie zobrazení, homotopická ekvivalence top. prostorù. Geometrický simpliciální komplex. Geometrická realizace. Triangulace. Triangulace sféry jako hranice simplexu a hranice crosspolytopu.

• 1.11. Abstraktní simpliciální komplexy. Geometrický simpliciální komplex indukuje abstraktní a naopak. Simpliciální zobrazení a jeho lineární (neboli afinní) roz¹íøení. Vlastnosti lineárního roz¹íøení (bez dùkazu). Barycentrická subdivize. Borsuk Ulamova vìta, rùzná znìní. Dùkaz ekvivalence (BU1a), (BU1b), (BU2a).
• 8.11. (JM) Ekvivalence zbývajících verzi Borsukovy-Ulamovy vìty. Lebesgueovo pokrývací lemma. Pøíklady simpliciálních komplexù, odvozených z kombinatorických a geometrických struktur (klikový komplex, ¹achovnicový komplex, nerv mno¾inového systému, øetìzcový komplex èásteènì uspoøádané mno¾iny, poznámka o "inverzní" konstrukci uspoøádané mno¾iny ze simpliciálního komplexu, slo¾ení tìchto dvou konstrukcí dá barycentrické podrozdìlení). Vìta: ka¾dý koneèný k-dimenzionální simpliciální komplex má geometrickou realizaci v dimenzi 2k+1 (pøes momentovou køivku).
• 15.11. (JM) Vìta o simpliciální aproximaci s dùkazem. Neformální úvod do homologie.
• 22.11. (JM) Definice homologie (koneèného) simpliciálního komplexu se Z_2 koeficienty (abychom byli nad tìlesem a nemuseli se starat o orientace): k-øetìzce, hranièní operátor, dva za sebou dávají nulu; k-cykly, k-hranice, H_k(K):=Z_k(K)/B_k(K) (cykly modulo hranice). Pøíklady (k dopoèítání): homologie n-simplexu a hranice n-simplexu; homologie 1-komplexu (grafu). Simpliciální zobrazení indukuje homomorfismy homologických grup. Definice: H_k(||K||) := H_k(K), cíl: je to korektní, nezávisí na triangulaci. Dùkaz trochu oklikou, neudìláme v¹echny kroky. Fakt: K' podrozdìlení K, pak H_k(K') je isomorfní H_k(K). Dùkaz jsme podrobnì nedìlali, potøebujeme z nìj: existuje simpliciální zobrazení g:K' do K, které je simpliciální aproximací identity na polyedru K, potom g_* indukuje ten isomorfismus, jeho inverze je indukována homomorfismem lambda: C_k(K) do C_k(K'). Nyní pro f:||K|| do ||L|| definujeme f_*:H_k(K) do H_k(L) jako slo¾ení s_*, kde s:K' do L je nìjaká simpliciální aproximace f, s lambda_*. Zase bychom chtìli, ¾e tato definice nezávisí na zvolené simpliciální aproximaci s a podrozdìlení K'. První krok = Lemma (bez dùkazu, cvièení): jsou-li s',s'' dvì simpliciální aproximace f na tém¾e podrozdìlení K', pak indukují toté¾ f_*.
• 29.11. (JM) Dal¹í (klíèové) lemma: K' a K" dvì podrozdìlení K, s',s" simpliciální aproximace f, pak zase definují toté¾ zobrazení v homologii. Dùkaz víceménì formání, s diagramem. Z toho u¾ snadno vìta: identické (spojité) zobrazení indukuje identické zobrazení v homologii, a pøechod od spojitých zobrazení k homomorfismùm v homologii komutuje se skládáním, tj. (fg)_* = f_* g_*. Dùsledek: je-li h homeomorfismus dvou polyedrù, pak h_* je isomorfismus homologických grup. Tedy homologie je topologický invariant. Podobnými metodami (simpliciální aproximací homotopie) se uká¾e, ¾e jsou-li f a g homotopická zobrazení, potom f_*=g_*. Tudí¾ homotopicky ekvivalentní prostory mají stejné homologické grupy. Definice stupnì zobrazení modulo 2 pro zobrazení f ze S^n do S^n (podle homomorfismu f_* v n-dim homologii - jsou jen dva mo¾né homomorfismy Z_2 do Z_2). Geometricky: stupeò je podle toho, zda má "generický" bod sudý nebo lichý poèet vzorù. Jednoduché aplikace homologie: S^m není homotopicky ekvivalentní S^n pro m rùzné od n; R^m není homeomorfní R^n; neexistuje retrakce koule na sféru; Brouwerova vìta o pevném bodì. Odvození Borsukovy-Ulamovy vìty z klíèového lemmatu: antipodální zobrazení S^n do S^n má lichý stupeò.
• 6.12. (MT) Odvození klíèoveho lemmatu z technického lemmatu (antipodální zobrazení z S^n do S^n je homotopicky ekvivalentní s (jiným) antipodálním zobrazením, které je navíc identické na rovníku). Pøipomenutí Kneserových grafù. Lovász-Kneserova vìta, Greenùv dùkaz tì¾¹í nerovnosti. Barevnost hypergrafu, barevnostní defekt, Doµnikovova vìta + dùkaz (analogie Greenova dùkazu). Schrijverovy grafy, Schrijverova vìta (zatím jenom znìní).
• 13.12. (MT) Galeho lemma. Odvození Lovász-Kneserovy vìty z Galeho lemmatu. Dùkaz Galeho lemmatu. Silnìj¹í verze Galeho lemmatu pro stabilní mno¾iny. Odvození Schrijverovy vìty ze silnìj¹í verze Galeho lemmatu. Ham-Sandwich Theorem - mìrová verze. Definice míry (sigma-algebry jenom náznakem). Borelovská míra. Dùkaz mìrové verze Ham-Sanwich Theorem (spojitost potøebného zobrazení zatím nedodìlaná).
• 20.12. (MT) Dokonèení dùkazu mìrové verze Ham-Sandwich Theorem (letmá zmínka o integrování pøes míru). Ham-Sandwich theorem pro bodové mno¾iny (+ dùkaz). Silnìj¹í verze pro mno¾iny bodù v obecné poloze (+ dùkaz). Dìlení míry v R^2 na 4 stejné èásti (+ zdùvodnìní), v R^3 na 8 èástí (bez zdùvodnìní), nemo¾nost v R^5 na 32 èástí pøes momentovou køivku. Akiyama-Alonova vìta (+ dùkaz), spravedlivé dìlení náhrdelníku mezi dva zlodìje (pøes momentovou køivku).
• 3.1. (MT) Pøipomenutí, ¾e grafy K_5 a K_{3,3} nejsou rovinné (1/2 Kuratowského vìty). d-skeleton (2d+2)-rozmìrného simplexu jako zobecnìní K_5. Spojení (join) abstraktních simpliciálních komplexù, vícenásobná spojení. Vícenásobné spojení dvojbodové diskrétní mno¾iny; pøipomenutí crosspolytopu a jeho hranice. Homeomorfní komplexy mají homeomorfní spojení (dùkaz plyne a¾ z následujících tvrzení). Spojení sféry a koule s jednobodovou a dvojbodovou diskrétní mno¾inou (dùkaz výsledku jenom pro dvojbodovou mno¾inu a sféru). Geometrické spojení. Geometrické spojení geometrických realizací dvou simpliciílních komplexù dává geometrickou realizaci (abstraktního) spojení tìchto dvou komplexù (v dùkazu jsme konstruovali pomocný geometrický komplex, ovìøení, ¾e se jedná o simpliciální komplex jsme pøevedli na tvrzení o konvexních obalech vhodných mno¾in, jeho¾ dùkaz jsme vynechali). Homeomorfní mno¾iny mají homeomorfní geometrické spojení. Vícenásobné spojení trojbodových diskrétních mno¾in jako zobecnìní K_{3,3}. Van Kampen - Floresova vìta.
• 10.1. (MT) Vícenásobné geometrické spojení, spojení zobrazení. Dùkaz Van Kampen - Floresovy vìty pro zobecnìné K_{3,3}.