1. Frobenius tétele teljes párosítás létezésére páros gráfokban. A Hall-feltétel és Hall tétele. A Frobenius és a Hall tételek ekvivalenciája. r reguláris gráf r db éldiszjunkt teljes párosítás egyesítése (Kőnig). (LPV 10. fejezet, EB 3.1,3.2,3.3, KRS 2.9.1.)

2. Deficites Hall-tétel (ha a Hall-feltétel d híján teljesül, akkor létezik A-t d híján fedõ párosítás. Kõnig tétele: független élek maximális száma = lefogó pontok minimális száma. (LPV 10.4., EB 3.4, 12.1, KRS 2.9.1)

3. Stabil párosítások, a Gale-Shapley algoritmus. Javító utak, majdnem javító utak, a Kõnig tétel bizonyítása majdnem javító utakkal. (AZ 28.)

4. Gráfparaméterek (független pontok max. száma, lefogó pontok min. száma, független élek max. száma, lefogó (vagy lefedõ) élek min. száma) és ezek kapcsolata: Gallai tételei. Párosítás tetszõleges gráfban: a Tutte tétel (biz. nélkül). (KRS 2.9.2., 2.9.3.)

5. Folyamok, maximális folyam-minimális vágás tétel. Kapcsolat javító utakkal. Egész értékűségi lemma, példák.

6. Minimax tételek. Menger tétel irányított éldiszjunkt utakra két pont között. A Menger tétel változatai (irányítatlan, él- vagy pontdiszjunkt). (EB 12.2, KRS 2.9.6.)

7. k-szoros pont- és élösszefüggõség és kapcsolatuk. Többszörös összefüggõség és a Menger tételek kapcsolata (biz. a "pont"-os változatban is, egy lemma gyakorlaton volt!). Kétszeres összefüggõség és két ponton/élen átmenõ kör létezése. Dirac tétele. (KRS 2.9.6.)

8. Állandó együtthatós lineáris rekurziók megoldása mértani sorozatok lineáris kombinációjaként. A karakterisztikus egyenlet, többszörös gyökök. Ötletek a rekurzió felállítására. (anyag a honlapomon)

9. Lineáris algebrai és generátorfüggvényes megoldás állandó együtthatós lineáris rekurziók megoldására. (anyag a honlapomon, KRS 7.2)

10. Tükrözési elv, Catalan-számok (a "Sor a pénztárnál" feladat, kétféle szemléltetése). A probléma megfogalmazása +1/-1 elemû sorozatokkal. A Catalan-számok explicit képlete. (anyag a honlapomon, KRS 7.5, de ott MÁS a def.!!!)

11. Rekurzió a Catalan-számokra. Catalan-számokra vezetõ nevezetes feladatok: n tényezõs szorzat zárójelezései, helyes zárójelezés. A Catalan-számok generátorfüggvénye. (anyag a honlapomon, KRS 7.5, de ott MÁS a def.!!!)

12. Ramsey tételei. Az R(k,l) Ransey-szám definíciója. R(3,3) meghatározása, R(k,l)<=R(k-1,l)+R(k,l-1) (Erdős-Szekeres), ennek segítségével a binomiális együtthatós felsõ becslés. (A becslés általában nem éles: R(3,4)=9). Az Erdõs féle alsó becslés. (anyag a honlapomon, KRS 2.12.1, EB 4.1, kicsit más jelölés!!, AZ 35.)

13. Többszínû Ramsey tételek, R(3,3,3)<=17, felsõ becslés az R(3,3,...,3)-ra. Felsõ becslések többszínû Ramsey-számokra: színösszevonás, illetve a sok 3-as bizonyítás lemásolása. (anyag a honlapomon, EB 4.4, 5.1, KRS 12.2.1)

14. Turán tételkör: Mantel tétele háromszögmentes gráf élszámáról. A probléma felvetése kizárt H részgráfra. Turán tétele kizárt teljes r+1 pontú részgráfra. r osztályú gráfok, a Turán-gráf. (anyag a honlapomon, EB 10.1, KRS 2.12.2. AZ 32.)

15. Felsõ becslés négy hosszú kört nem tartalmazó gráfok élszámára (V betûk ill. cseresznyék számolása). Példa cn^(3/2) élt tartalmazó (páros) gráfra (Klein Eszter): projektív sík modulo p. Zarankiewicz problémája. (anyag a honlapomon, EB 10.3, LPV 14.1, 14.2 motivációt ad a geometriákhoz)

16. Lineáris algebrai módszerek alkalmazása gráfokra: adott bőségű reguláris gráfok, a Hoffman-Singleton tétel 5 bőség esetére. A Barátság tétel (Erdős, Rényi, T.Sós) (ez most biz. nélk.) (anyag a honlapomon, AZ 34.)

17. Halmazrendszerekre vonatkozó extremális kérdések: Sperner-rendszerek, Sperner tétele (visszavezetés a Hall-tételre) (anyag a honlapomon, EB 13.1, AZ 23)

18. A LYM (YBL M) egyenlõtlenség, a Sperner tétel második biz. Erdõs-Ko-Rado tétele. (EB 13.1, KRS 8.1, AZ 23.)

-------------------------------------------------------------

Ajánlott irodalom:
LPV: Lovász László, Pelikán József, Vesztergombi Katalin: Diszkrét matematika, Typotex Kiadó, 2006.

EB: Elekes György, Brunczel András: Véges matematika, Eötvös Kiadó, 2006

KRS: Katona Gyula, Recski András, Szabó Csaba: Bevezetés a számítástudományba, Typotex Kiadó

AZ:M. Aigner, G. Ziegler, Bizonyítások a könyvből, Typotex Kiadó, 2004.