1. Kőnig tétele: független élek maximális száma = lefogó pontok minimális száma. Javító utak, majdnem javító utak, a Kõnig tétel bizonyítása majdnem javító utakkal. (LPV 10.4., EB 3.4, 12.1, KRS 2.9.1)

2. Stabil párosítások, Gale-Shapley algoritmus (csak a legegyszerűbb esetben). (jegyzet honlapon, AZ)

3. Súlyozott párosítások, Kőnig-Egerváry algoritmus. (jegyzet a Temasben, Frank András anyag a magyar módszerről a honlapján)

4. Gráfparaméterek (ismétlés): Gallai tételei. Párosítás tetszõleges gráfban: a Tutte tétel (KRS 2.9.2., 2.9.3., Teams-es anyag is)

5. Hálózatok, folyamok. Ford-Fulkerson (maximális folyam-minimnális vágás). (KRS 2.9.4., EB)

6. A Menger tétel változatai (irányítatlan, él- vagy pontdiszjunkt) és a folyamok kapcsolata. (EB 12.2, KRS 2.9.6.) Elemi bizonyítás a pontdiszjunkt esetre. (Göring cikk, Discrete Math., KRS, EB)

7. k-szoros pont- és élösszefüggõség és kapcsolatuk, kapcsolat a Menger tételekkel. Dirac tétele. (KRS 2.9.7, EB)

8. Ramsey tételei két színre a gráfos verzióban. Becslések R(k,l)-re (Erdős-Szekeres). (anyag a honlapon, KRS 2.12.1, EB 4.1, kicsit más jelölés!!)

9. Többszínû Ramsey tételek, felsõ becslések többszínû Ramsey-számokra: színösszevonás, illetve a sok 3-as bizonyítás lemásolása (Erdős-Szekeres). (anyag honlapon, EB, KRS)

10. Végtelen Ramsey-tétel. Kőnig-lemma végtelen utakról. Véges és végtelen Ramsey tételek kapcsolata. (EB)

11. Ramsey tétele r-esek színezésérõl, a végtelen és a véges esetben. (EB)

12. Erdõs-Szekeres tétel nagy konvex sokszög létezésérõl. (anyag a honlapomon, EB 4.4, 5.1)

13. Turán tételkör: Mantel tétele, Turán tétele, a Turán-gráf. (anyag a honlapomon, EB 10.1, KRS

14. Felsõ becslés négy hosszú kört nem tartalmazó gráfok élszámára. Példa cn^(3/2) élt tartalmazó (páros) gráfra (Klein Eszter): koordináta-geometria (affin sík) modulo p. (anyag a honlapomon, EB 10.3, LPV 14.1, 14.2 motivációt ad a geometriákhoz)

15. Zarankiewicz problémája, Reiman tétele (az extrém gráf projektív sík illeszkedési gráfja.) (ÚMM)

16. Adott bőségű reguláris gráfok, alsó és felső becslés a csúcsszámra. A g=6 eset és projektív síkok (Kárteszi, Reiman). (ÚMM)

17. 5 bőségű reguláris gráfok, Hoffman-Singleton tétel (gyakorlaton volt, jegyzet a honlapon).

18. A barátság tétel. A C_4-mentes gráfokra vonatkozó felső becslésben (Erdős) nem lehet egyenlőség. (AZ)

19.(Nem-uniform) Fisher-egyenlőtlenség (blokkrendszeres és metszet-tételes változatban). De Bruijn-Erdős. (ÚMM)

20. Négyzetes blokkrendszerek, ezekben két blokk metszete lambda. Szükséges feltétel négyzetes blokkrendszer létezésére (Schützenberger).

21. Teljes gráf felbontása teljes és teljes páros részgráfokra (Graham-Pollak). (ÚMM)

22. Halmazrendszerekre vonatkozó extremális kérdések: Sperner-rendszerek, Sperner tétele (visszavezetés a Hall-tételre), kapcsolat Dilworth tétellel. (EB 13.1, KRS)

23. A LYM (YBL M) egyenlõtlenség, a Sperner tétel második biz. Egyenlőség a LYM egyenlőtlenségben(EB 13.1, KRS 8.2)

24. Bollobás tétele keresztben metsző halmazrendszerekrõl. Kapcsolat a Sperner tétellel.

25. Erdõs-Ko-Rado tétele. (EB 13.1, KRS 8.1)

26. Ray-Chaudhuri-Wilson tétel és mod p változatai. (EB)

27. Kruskal-Katona (árnyékok), a tétel Lovász féle változata Biz.-sal. (a Katona-féle anyag a Teams-ben)

28. Borsuk probléma. (EB)

29. Generátorfüggvények, állandó együtthatós lineáris rekurziók megoldása. (KRS, EB, tanárszakos anyag honlapon)

30. Catalan-számok, tükrözési elv. Rekurzió Catalan-számokra. Catalan-számok generátorfüggvénye, az explicit képlet a generátorfüggvényből. (EB, KRS, de ott más a jelölés!!!, anyag honlapon)

31. Stirling-számok, kapcsolatuk, generátorfüggvény(eik). (KRS)

32. A Bell-számok exponenciális generátorfüggvénye. (KRS)

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

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 Y. Gyula, Recski András, Szabó Csaba: Bevezetés a számítástudományba, Typotex Kiadó

ÚMM: Hraskó András (szerk.) Új matematikai mozaik, Typotex

Ezek általában többet tartalmaznak az anyagról, mint amit mi vettünk, de bizonytalanság esetén segítenek a tételek, definíciók pontos kimondásában. Igyekszem minél több témáról a mi tárgyalásunkat követõ anyagot feltenni a honlapomra (ezek is gyakran tartalmaznak picit többet annál, mint ami szükséges).

A vizsga menete olyan lesz, mint az első félévben.