Véges mat I

Előadás helye: Déli Tömb 00.623, ideje: hétfő 2:10-3:50

Könyv (részben fedi az előadást): Lovász - Pelikán - Vesztergombi: Diszkrét Matematika

Jegyzetek:

A Kuratowski Tétel bizonyítása

A Kruskal-Katona Tétel bizonyítása

Hetenkénti téma

Február 11.
Gráfok kétszeres élösszefüggősége és pontösszefüggősége. Kétszeresen összefüggő komponensek és kaktusz-felbontás. Fülfelbontás és alkalmazásai: erősen összefüggővé irányíthatóság; másodfokú csúcsok minimális 2-szeresen összefüggő gráfokban.
Február 18.
Folyamok irányított gráfokon. Vágások, javító utak. Max-folyam-min-vágás tétel. Egészértékûségi tétel. Javító utas algoritmus: végtelen is lehet, de a legrövidebb utat választva polinomiális (bizonyítás nélkül). Pontkapacitások.
Február 25.
Menger tétele (4 változat). Menger tétele halmazok közötti utakra. Adott pontpárokat összekötõ utak problémája (csak példa). k-szorosan összefüggõ gráfok és jellemzésük. Adott k csúcson átmenõ kör létezése.
Március 4.
Minorok, topologikus részgráfok. Soros-párhuzamos gráfok jellemzése kizárt teljes 4-essel. Kuratowski tételének kimondása, a minorral és toplogikus részgráffal való jellemzés ekvivalenciája.
Március 11.
Gallai-azonosságok, Tutte-tétel, fülfelbontás faktorkritikus gráfokra, Gallai-lemma faktorkritikus gráfokra, ez utobbira alkalmazas: összefüggõ csúcstranzitív gráfban vagy van teljes párosítas vagy faktorkritikus.
Március 18.
Kuratowski tételének bizonyítása. Háromszorosan összefüggõ gráfok síkbarajzolása egyértelmû.
Csúcsok részhalmazának foka, erre vonatkozó egyenlõtlenség (szubmodularitás). Szoros halmazok és zártságuk metszetre és únióra. Minimális k-szorosan élösszefüggõ gráfban van k-adfokú csúcs.
Március 25.
A maximális párosítás mérete (Berge formula). Minden G gráfnak van legfeljebb 2tau(G) csúcsú, legfeljebb tau(G)(tau(G)+1)/2 élû részgráfja, melynek a tau-ja ugyanaz. Bizonyítás (az élszámra) lineáris algebrai módszerrel.
Intervallum-rendszerekre vonatkozó min-max tételek. Lefordításuk intervallum-gráfok nyelvére.
Április 8.
Dilworth tétele parciálisan rendezett halmazokra. Minden irányított gráf lefedhetõ alpha(G) irányított úttal (Gallai-Milgram tétel).
Extremális halmazrendszerek, Sperner tétele. Két bizonyítás: 1. véletlen sorbarakás, LYM egyenlõtlenség. 2. A Boole algebra lefedhetõ szimmetrikus láncokkal.
Április 15.
Erdõs-Ko-Rado tétel. De Bruijn-Erdõs tétele és a Fischer egyenlõtlenség, 2 bizonyítással. Párosfalva tétele. Halmazrendszerek, melyben bármely két halmaz vagy tartalmazza egymást vagy diszjunkt, kapcsolatuk fákkal.
Április 22.
A bizonyítás befejezése. Bollobás-egyenlõtlenség. A Kruskal-Katona tétel motiválása, számok binomiális felírása.
Május 6.
Alapvetõ generátorfüggvények (binomiális sorozat, exponenciális), Catalan-számok generátorfüggvénye, Bell-számok exponenciális generátorfüggvénye, "snake oil" módszer szummák egyszerûbb alakra hozására két példával, partíciók generátorfüggvényei, páratlan=különbözõ partíciók két bizonyítással, Euler-féle ötszögszám tétel bizonyítás nélkül generátorfüggvényes alakban felírva.
Május 13.
A Kruskal-Katona tétel kimondása és gyengébb változat bizonyítása. Turán-probléma 3-uniform hipergráfokra (sejtés kimondása). Hipergráfok szinezhetõsége (definíció).
Május 16.
Hipergráfok színezhetõsége: két élnek nem 1 közös pontja van; bármely két élnek van közös pontja; korlát az élek számára; bármely k él legalább k+1 pontot fed le.

Last modified May 16, 2013.