- Előadás helye: Északi Tömb 7.59, ideje: péntek 12:15-13:45
-
Hetenkénti téma
Szeptember 14.
Lineáris algebrai összefoglaló: Szemidefinit mátrixok és jellemzésük, Perron-Frobenius Tétel, sajátértékek elválasztása. Gráfok mátrixai: Adjacencia-mátrix, Laplace-mátrix. A Laplace-mátrix pozitív szemidefinit. Gráfok sajátértékei: teljes gráfok, csillagok, körök, kockák. A legnagyobb sajátérték: egyszerű korlátok.Szeptember 21.
Legnagyobb sajátérték és legnagyobb klikk. Legkisebb sajátérték. Páros gráfok jellemzése a legkisebb sajátértékkel. Hoffman becslése a kromatikus számra. Élgráfok spektruma és a legkisebb sajátérték. A sajátérték-hézag. Expanderek, konduktancia, és sajátérték-hézag kapcsolata. Alon-Milman és Jerrum-Sinclai tételek kimondása, a könnyű irány bizonyítása az utóbbiban.Szeptember 28.
A Sinclair-Jerrum Tétel bizonyítása. Bolyongás gráfokon. Nem-páros összefüggő gráfon a bolyongás kever. Keverési sebesség és sajátérték-hézag kapcsolata.Október 5.
Gráfok sajátértékeinek száma: mikor maximális (mind különböző), mikor minimális (legfeljebb 3). Barátság-tétel. Ortogonális reprezentáció, példák. Általános helyzetű ortogonális reprezentáció, a minimális dimenzió jellemzése. A bizonyítás kezdete.Október 12.
Minimális dimenzió jellemzésének bizonyítása. Theta-függvény definícója, egyszerű tulajdonságai. Alkalmazás a Shannon-kapacitásra.Október 19.
Theta-függvény jellemzése spektrummal és szemidefinit programmal. Következmények: komplementer gráf theta-függvénye általában és csúcstranzitív gráf esetén.Október 26.
Csúcstranzitív, önkomplementer gráfok thetája és Shannon kapacitása. A theta-függvény multiplikativitása. Az ortogonális reprezentációk varietása, annak reducibilitása. A kocka komplementeréhez tartozó varietás. (Nem bizonyítottuk.) alpha(G) alsó becslése theta(G komplementer) segítségével. Alkalmazás: 3-kromatikus gráf szinezése kevés színnel. (Bizonyítás csak vázlatosan.)November 9.
Regularitási Lemma, standard és gyenge változat. Mátrixos megfogalmazás, vágástávolság azonos halmazon értelmezett gráfok között. A lemma bizonyítása.November 16.
A lemma ekvipartíciókra. Homomorfizmus-sűrűségek, egyenlőtlenségek. Megszámolási Lemma. Elhagyási Lemma.November 23.
Elhagyási lemma következményei: nem-algebrai összefüggés részgráf-sűrűségek között, fráftulajdonságok tesztelhetősége. Az extremális gráfelmélet alaptételei (Erdős, Stone, Simonovits) a regularitási lemma alkalmazásaként.November 30.
A hasonlósági távolság. Gyenge regularitási partíciók, mint reprezentatív halmazok Voronoi-cellái, bizonyítás az egyik irányban.December 7.
A bizonyítás befejezése. Alkalmazások: regularitási partíció konstruálása a mintavételi modellben, elégésges feltétel polinomiális méretű regularitási partíció létezésére.
Jegyzet (részben fedi az előadást):
Geometric Representations of Graphs
3. fejezet (Harmonic functions on graphs), 9. fejezet (Orthogonal representations), 13.4 és 13.6. alfejezetek (lineáris algebra, gréfok sajátértékei)
Használható még:
Large networks and graph limits
9.1, 10.5, 11.8.2 és 15.4 alfejezetek.