- Előadás helye: Déli Tömb 1.819, ideje: Csütörtök 12:15-13:45
- Segédanyagok:
L. Lovász: Large networks and graph limits 5.1-5.4, 5.6, 5.6, 5.7
L. Lovász: Characterization of homomorphism functions (Jegyzetek)
Brightwell-Winkler: Graph homomorphisms and long range action
L. Lovász: Topological Methods in Combinatorics (Jegyzetek)
-
Hetenkénti téma
Szeptember 12.
Homomorfizmus létezése adott célgráfba, példák polinomiális és NP-teljes esetekre. Dichotómia-tétel (csak kimondva). Homomorfizmusok száma, izomorfia jellemzése homomorfizmus-számmal, gyökvonás egyértelműsége, szorzat rövidítése.Szeptember 19.
Homomorfizmus-számok, speciális esetek: fokszámok momentumai, spektrum momentumai, kromatikus polinom, maximális vágás (közelítőleg), páros fokúság jellemzése. Möbius-inverzió és Möbius-függvény parciálisan rendezett halmazokon.Szeptember 26.
Kapcsolási mátrixok, homomorfizmus-függvények jellemzése. A szükségesség bizonyítása, az elégségesség bizonyításának elkezdése: gráfalgebrák és tulajdonságaik.Október 3.
Felső és alsó becslés a gráfalgebrák dimenziójára. Izomorfia R^d-vel, idempotens bázis. Nem-egyszerűsíthető idempotensek, végességük.Október 10.
A bizonyítás befejezése. Duális karakterizáció, a nyilak megfordítása, kitekintés a lokálisan véges kategóriák elméletére. A Hom gráf és a Hom komplexus definíciója.Október 17.
Hom gráf: példák. Mikor összefüggő a Hom gráf? Hom(K_2,G), Hom(C_n,G). Brightwell-Winkler tétele: Ha Hom(F,G) összefüggő minden F-re, melynek minden fokszáma kisebb mint 2d, akkor G kromatikus száma legalabb d+2.Október 24.
A Brightwell-Winkler tétel bizonyításának befejezése. A Hom komplexus definíciója, magasabb topológikus összefüggőség és kromatikus szám.November 7.
Kombinatorikus homotópia-elmélet elemei. Szimpliciális komplexus, szimpliciális leképezés, geometriai realizáció, baricentrikus felbontás, retraktum, homotópia, homotópikus ekvivalencia, kontrahálhatóság, topológikus összefüggőség. Kontrahálhatóság jellemzése.November 14.
Ideg-tétel. A kontrahálhatósági lemmák és tételek kiterjesztése topológikus öszefüggésre.November 21.
A szomszédsági és Hom komplexusok kapcsolata. Kromatikus szám becslése topológikus összefüggéssel. Alkalmazás a Kneser-gráfra.November 28.
Sperner Lemma, Brouwer fixponttétel. Zárkózott gráftulajdonságok, példák.December 5.
Zárkózótt Boole-függvények. Minden nemkonstans, monoton Boole-függvény zárkózott, ha az automorfizmus-csoportja tranzitív, és a változók száma prim. Minden nemtriviális, monoton gráftulajdonság zárkózott, ha a csúcsok száma prím. (A zárkózottságról algoritmuselméleti szempontból itt lehet olvasni: L. Lovász: Complexity of algorithms, 12.4December 12.
Borsuk-Ulam tétel alkalmazásai: Sonkásszendvics (Ham-Sandwich) tétel, nyaklánc-probléma.