Informace k prednasce "Topologicke metody v kombinatorice" 
(Jiri Matousek, KAM) 2007/2008

Zkouska

CTVRTEK od 9:00 v S7, cviceni zhruba 1x za 14 dni pred prednaskou (po domluve), zaciname 4.rijna

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

Literatura

J. Matousek: Using the Borsuk-Ulam theorem, Springer 2003. Na teto strance jsou i nektere kapitoly v elektronicke podobe

Starsi skripticka J. Matousek: Topologicke metody v kombinatorice a geometrii, KAM Series 94-272c, nektere veci delane trochu jinak nez v prednasce, casto mene podrobne.

Na webu je k dispozici velmi pekny uvod do algebraicke topologie od Allena Hatchera, viz
 http://www.math.cornell.edu/~hatcher/ .

Probrana latka

Prednaska 4.10.2007. Zakladni pojmy obecne topologie: topologicky prostor, podprostor, spojite zobrazeni, homeomorfismus. Uzavrena mnozina, uzaver a hranice mnoziny. Soucinova topologie. Hausdorffovsky prostor. Kompaktni prostor, kompaktni mnozina. Veta o vlastnostech kompaktnosti (1. uzavrena podmnozina kompaktni mnoziny je kompaktni; 2. kompaktni podmnozina v hausdorffovskem prostoru je uzavrena; 3. obraz kompaktni mnoziny pri spojitem zobrazeni je kompaktni; 4. spojita realna funkce na neprazdne kompaktni mnozine nabyva minima; 5. podmnozina R^d je kompaktni, prave kdyz je uzavrena a omezena).

Prednaska 11.10.2007. Dukaz vety o vlastnostech kompaktnosti. Zneni Tichonovovy vety: libovolny soucin kompaktnich prostoru je kompaktni (obecne se na to potrebuje axiom vyberu). Pojem souvislosti a obloukove souvislosti topologickeho prostoru; priklad s krivkou sin(1/x), ktery je souvisly a neni obloukove souvisly (bez dukazu). Snahou topologie je klasifikovat prostory podle homeomorfismu (napr. to, ze R^n neni homeomorfni R^m pro m ruzne od n je pomerne tezke dokazat!), v algebraicke topologii se vetsinou pouziva hrubsi ekvivalence = homotopicka ekvivalence. Nejdriv pripravny pojem: deformacni retrakt jako specialni pripad homotopicke ekvivalence. Homotopie zobrazeni, homotopicka ekvivalence prostoru. Tvrzeni bez dukazu: prostory X a Y jsou homotopicky ekvivalentni, prave kdyz existuje Z takovy, ze jak (homeomorfni kopie) X, tak (homeomorfni kopie) Y jsou deformacnimi retrakty Z. Pojmy: kontrahovatelny prostor (= homotopicky ekvivalentni bodu), nulhomotopicke zobrazeni (= homotopicke nejakemu konstantnimu zobrazeni).

Prednaska 18.10.2007. Afinni nezavislost bodu v R^n. Simplex, stena simplexu. Geometricky simplicialni komplex. Jeho dimenze. Podkomplex. Fakt: vsechny steny simplexu tvori simplicialni komplex (bez dukazu, neni tezke). Polyedr simplicialniho komplexu, definice jeho topologie platna i v nekonecnem pripade. My budeme uvazovat jen konecne simplicialni komplexy. Triangulace topologickeho prostoru. Priklady: triangulace sfery jako hranice simplexu a jako L1-sfery. Abstraktni simplicialni komplex, jeho geometricka realizace. Simplicialni zobrazeni abstraktnich simplicialnich komplexu, jejich isomorfismus. Afinni rozsireni simplicialniho zobrazeni na polyedry geometrickych realizaci. Bez dukazu: afinni rozsireni je spojite zobrazeni polyedru, z prosteho simplicialniho zobrazeni se dostane proste afinni rozsireni a z isomorfismu homeomorfismus. Dusledek: isomorfni simplicialni komplexy maji homeomorfni polyedry.

Prednaska 25.10.2007. Priklady zajimavych simplicialnich komplexu:

• Klikovy komplex grafu.
• Nerv mnozinoveho systemu, specialne systemu konvexnich mnozin v R^d [fakt: pro konvexni mnoziny je polyedr nervu homotopicky ekvivalentni sjednoceni tech mnozin].
• Retezcovy komplex (order complex) \Delta(P) castecne usporadane mnoziny P.
• Sachovnicovy komplex (simplexy = postaveni vezi na sachovnici takova, ze zadne 2 veze nejsou ve stejne rade nebo sloupci).
• Hranice simplicialniho konvexniho mnohostenu.

• (BU1a) Pro kazde spojite zobrazeni f sfery S^n do R^n existuje x, pro nez f(-x)=f(x).
• (BU1b) Pro kazde spojite antipodalni zobrazeni f sfery S^n do R^n (tj. f(-x)=-f(x)) existuje x, pro nez f(x)=0.
• (BU2a) Neexistuje spojite antipodalni zobrazeni S^n do S^{n-1}.
• (BU2b) Neexistuje spojite zobrazeni B^n do S^{n-1} antipodalni na hranici B^n.
• (LS-c) [Ljusternik-Snirelman] Pro kazde pokryti S^n n+1 uzavrenymi mnozinami obsahuje jedna z mnozin dvojici antipodalnich bodu.
• (LS-o) Totez pro pokryti n+1 otevrenymi mnozinami.

Prednaska 1.11.2007. Ekvivalence vsech 6 verzi Borsukovy-Ulamovy vety. Brouwerova veta o pevnem bode, jeji dukaz z (BU2b). Tuckerovo lemma a jak z nej plyne (BU2b). Jina formulace Tuckerova lemmatu (o simplicialnich zobrazenich do simplicialniho komplexu \Diamond^{n-1}).

Prednaska 8.11.2007. Dukaz Tuckerova lemmatu: pojem k-retezce, nektere vlastnosti. Simplicialni zobrazeni sfery do sfery stejne dimenze: sudy a lichy stupen. Jde-li takove simplicialni zobrazeni rozsirit na celou kouli, pak ma sudy stupen. Je-li takove simplicialni zobrazeni antipodalni, pak ma lichy stupen. Zde ucebni text k tomuto dukazu.

Prednaska 15.11.2007. Veta o sendvici "spojita" (pro konecne borelovske miry, pro nez ma kazda nadrovina miru 0). Definice "nadrovina puli konecnou mnozinu", veta o sendvici "diskretni" (pro konecne bodove mnoziny), dukaz jen pro mnoziny v obecne poloze. Technicke zesileni pro mnoziny v obecne poloze. Strucny prehled o problemech "krajeni na stejne velke kusy" (1 miru v R^d na 2^d kusu pomoci d nadrovin: d=2,3 lze, d=5 a vic nelze, d=4 velky otevreny problem; krajeni 2 mer "4-vejirem" a dalsi priklady). Veta Akiyamova-Alonova.

Prednaska 22.11.2007. Veta o nahrdelniku (pro 2 zlodeje). Kneserova domnenka, zminka o zlomkove barevnosti Kneserovych grafu. Lovaszova-Kneserova veta. Prvni dukaz (Greene). Zobecneni (Dolnikov-Kriz), defekt 2-obarvitelnosti mnozinoveho systemu. Druhy dukaz (Barany) - z Galeova lemmatu.

Prednaska 29.11.2007. Dukaz Galeova lemmatu (pomoci momentove krivky umistene do R^{d+1}). Schrijveruv graf, dolni odhad jeho barevnosti (z uvedeneho dukazu Galeova lemmatu a Baranyovy metody plyne ihned). Pojmy: (volny) Z_2-prostor, Z_2-akce, Z_2-zobrazeni. Podobne pro konecnou nebo kompaktni topologickou grupu G: G-prostor, G-zobrazeni. Z_2-simplicialni komplex (Z_2-akce dana simplicialnim zobrazenim, tj. automorfismem komplexu). Priklad: sd(simplex bez vnitrku), simplicialni Z_2-akce dana doplnkem. Definice simplicialniho Z_2-komplexu B(G) pro graf G, homomorfismus G do H indukuje Z_2-zobrazeni B(G) do B(H), specialne m-obarveni G indukuje Z_2-zobrazeni B(G) do B(K_m).

Prednaska 13.12.2007.

• Definice Z_2-indexu ind(X) a Z_2-koindexu coind(X) pro Z_2-prostor X (miry "velikosti" X).
• Jednoduse videt: ind(X)>ind(Y) implikuje, ze X nelze Z_2-zobrazit do Y (podobne pro coind).
• Z Borsukovy-Ulamovy vety: coind(X) <= ind(X), ind(S^n)=coind(S^n)=n.
• Existuji Z_2-prostory, pro nez coind(X) < ind(X), ale neni snadne na ne prijit (a dokazat to).
• k-souvislost: definice (2 verze, pomoci rozirovani ze sfery na kouli a pomoci nulhomotopie). S^n je (n-1)-souvisla ale ne n-souvisla (prvni cast jen naznak dukazu).
• Je-li X n-souvisly, pak coind(X)>= n+1. Dukaz: rozsirovani zobrazeni na S^0,S^1,S^2,... indukci podle dimenze.
• Je-li K volny simplicialni Z_2-komplex, pak ind(K) <= dim(K). Dukaz podobny jako v predchozim bode, s vyuzitim (n-1)-souvislosti S^n.
• Pripomenuti B(G) a trochu jiny pohled na nej. B(K_m) je oktaedralni (m-1)-sfera bez dvou protilehlych faset, tudiz ind(B(K_m))=m-2. Odtud veta (doni odhad barevnosti): chi(G) >= ind(B(G))+2 pro kazdy graf G.

Prednaska 20.12.2007.

• Komplex okoli (neighborhood complex) N(G). Je homotopicky ekvivalentni B(G) (bylo ve cviceni). Tudiz: je-li N(G) k-souvisly, ma G barevnost aspon k+3 (puvodni Lovaszova veta).
• Zobecnena Mycielskeho konstrukce M_r(G). Veta [Gyarfas-Jensen-Stiebitz]: Pro kazde r a kazdy graf G je N(M_r(G)) homotopicky ekvivalentni susp(N(G)) (bez dukazu). Zde suspenze susp(X) = "dvojity kuzel" nad X; pro simplicialni komplex K je susp(K)=K*S^0, kde * je spojeni (join) zavedeny nize. Zacneme-li tedy napr. z liche kruznice, iteraci operace M_r dostavame komplexy okoli homotopicky ekvivalentni sferam. To dava zajimave grafy velke barevnosti.
• Uvod do nevnoritelnosti: mame simplicialni komplex K, chceme ukazat, ze neexistuje proste spojite zobrazeni f:||K|| -> R^d pro vhodne d. (Priklad: K = graf K_{3,3} nebo K_5, d=2.) Silnejsi verze: pro kazde spojite f:||K||-> R^d existuji x,y z ||K|| s disjunktnimi nosici, pro nez f(x)=f(y); zde nosic supp(x) je simplex K minimalni dimenze obsahujici x.
• Jeden pristup, ktery jsme jen nacrtli pro pripad K=trojuhelnik, d=1: utvorit mnozinu X={(x,y): x,y\in ||K||, x,y maji disjunktni nosice}. To je volny Z_2-prostor (akce=zamena souradnic), a zobrazeni posilajici (x,y) na (f(x),f(y)) ho Z_2-zobrazi do Y=R^d x R^d \ {(x,x): x\in R^d} (tedy za predpokladu, ze f(x) je ruzne od f(y) kdykoliv x a y maji disjunktni nosice). Pro dukaz nevnoritelnosti staci ukazat, ze ind(X)>ind(Y). To jsme v pripade K=trojuhelnik, d=1 overili.
• Ve slozitejsich prikladech je uvedena konstrukce X obtizne zvladnutelna. Lepsi vlastnosti ma tzv. mazane spojeni (deleted join).
• Spojeni (join) simplicialnich komplexu. Mazane spojeni. Jednoduche priklady.
• Geometricka reprezentace polyedru ||K*L|| (K a L se umisti v mimobeznych podprostorech, body ||K*L|| pak vyplni vsechny usecky spojujici bod z K s bodem z L).

Prednaska 3.1.2008.

• Veta o nevnoritelnosti: pokud ind(mazane spojeni K) je aspon d+1, potom kazde spojite zobrazeni polyedru K do R^d ztotozni dva body s disjunktnimi nosici. Dukaz sporem: kdyby existovalo "spatne" zobrazeni, udelame z nej Z_2-zobrazeni mazaneho spojeni do R^{d+1}, ktere nic nezobrazi na 0 (tohle zobrazeni se konstruuje trikem: bod tx+(1-t)y mazaneho spojeni se zobrazi na bod (1-2t, tf(x)-(1-t)f(y)) z R^{d+1}).
• Priklad: topologicka Radonova veta (pro K = simplex na n vrcholech, d=n-2).
• Kombinatoricky dolni odhad na ind(mazane spojeni K): Pro dany simplicialni komplex K definujeme F(K) jako system vsech "minimalnich nesimplexu" K, tj. system vsech mnozin z 2^V\K minimalnich vzhledem k inkluzi, kde V je mnozina vrcholu K. Sarkariova veta: Pokud d je nejvys n-chi(KG(F(K)))-2, potom kazde spojite zobrazeni ||K|| do R^d ztotozni dva body s disjunktnimi nosici. Zde chi(KG(.)) je barevnost Kneserova grafu.
• Priklad: pro K=K_{3,3} je F(K) mnozina dvojic, totiz vsech nehran grafu K_{3,3}, a jeji Kneseruv graf je 2-barevny. Sarkariova veta da nerovinnost K_{3,3}.
• Priklad: Van Kampenova-Floresova veta: d-skelet (2d+2)-dimenzionalniho simplexu se neda vnorit do R^{2d} (pro d=1 je to nerovinnost grafu K_5). (Pritom kazdy d-dimenzionalni simplicialni komplex se da geometricky realizovat v R^{2d+1}.) Prislusny Kneseruv graf je diskretni a ma barevnost 1.
• Lemma: ind(X*Y) je nejvys ind(X)+ind(Y)+1. Zde X,Y jsou simplicialni Z_2-komplexy. K dukazu je potreba overit, ze S^k*S^m je homeomorfni S^{k+m+1} (to se da udelat napr. pro oktaedralni triangulace tech sfer), a taky definovat join dvou Z_2-zobrazeni.
• Lemma: Je-li L_0 nejaky simplicialni Z_2-komplex a L jeho simplicialni Z_2-podkomplex (na teze mnozine vrcholu), potom ind(L) >= ind(L_0)-ind(Delta(L_0\L))-1, kde Delta(.) je retezcovy komplex mnozinoveho systemu vzhledem k usporadani inkluzi. Dukaz: kanonicke simplicialni Z_2-vnoreni sd(L_0) do sd(L)*Delta(L_0\L), coz je kombinatoricky trivialni zalezitost, plus predchozi lemma o ind(X*Y).
• V dukazu Sarkariovy vety se predchozi lemma pouzije pro L=mazane spojeni K a L_0=mazane spojeni uplneho simplexu. Zbyva SHORA odhadnout ind(Delta(L_0\L)) pomoci obarveni Kneserova grafu.