- Előadás helye: Északi Tömb 0.87 Marx terem, ideje: csütörtök 8:15-10:00
- Jegyzet (részben fedi az előadást): Elekes György-Bunczel András: Véges Matematika
-
Hetenkénti téma
Február 15.
König-Hall tétel deficites alakja, König tétele, páros gráfok élszínezése, Gallai azonosságok.
Február 22.
Párosítások nem-páros gráfban. Tutte tétele.
Március 1.
Tutte tételének alkalmazásai: Berge formula, Petersen tétele. Élszinezés, négyszíntétel élszinezéses alakja.
Március 8.
Folyamok. Minimális-Folyam-Maximális-Vágás Tétel. Javító út. Egész kapacitások esetén létezik egész maximális folyam. Pontkapacitásos változat.
Március 22.
Minimális-Folyam-Maximális-Vágás Tétel alkalmazásai: új bizonyítás König tételére, Menger tétele (4 alakban). k-szoros összefüggőség, k ponton átmenő kör k-szorosan összefüggő gráfban, topologikus K_4 3-szorosan összefüggő gráfban.
Március 29.
Fák leszámlálása. Adott fokú fák száma, Cayley formula. Prüfer kód, G gráf feszítőfáinak száma (Cauchy-Binet formula kimondása).Április 12.
Síkgráfok, Euler formula (ismétlés). 2-szeresen összefüggő síkgráf lapjait körök határolják. Kuratowski tétele, a bizonyítás kezdete. Bizonyítás (pdf)
Április 19.
Kuratowski tételének bizonyítása. Háromszorosan összefüggő síkgráf egyértelműen rajzolható síkba. Erősen összefüggő irányított gráfok, erősen összefüggő komponensek. Erősen összefüggő gráfok fülfelbontása. 2-szeresen (él)összefüggő gráfok fülfelbontása. Robbins tétele: egy irányítatlan gráfnak akkor és csak akkor van erősen összefüggő irányítása, ha 2-szeresen élösszefüggő.
Április 26.
Cauchy-Binet formula bizonyítása. Catalan számok.
Május 3.
Extremális halmazrendszerek. Sperner tétele, bizonyítás átlagolással és láncfelbontással. Erdős-Ko-Radó tétel. Erdős-De Bruijn egyenlőtlenség.
Május 17.
Napraforgót nem tartalmazó hipergráfok (Erdős-Rado tétele). Turán probléma hipergráfokra. Bollobás tétele, két bizonyítással (átlagolás, polinom-módszer). Alkalmazás tau-kritikus hipergráfra.