1. Frobenius tétele teljes párosítás létezésére páros gráfokban. (Bizonyítás az élek száma szerinti indukcióval). 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). (anyag a honlapomon, LPV 10. fejezet, EB 3.1,3.2,3.3, KRS 2.9.1.) ABSZOLÚT MINIMUM: Hall-tétel, Frobenius- és Hall-tétel kapcsolata, a definíciók.

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. Javító utak, majdnem javító utak, algoritmus maximális független élrendszer keresésére. (biz. nélk.) (anyag a honlapomon, LPV 10.4., EB 3.4, 12.1, KRS 2.9.1) ABSZOLÚT MINIMUM: Kőnig tétele, deficites Hall -tétel, a definíciók.

3. 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). (anyag a honlapomon, KRS 2.9.2., 2.9.3.) ABSZOLÚT MINIMUM: Gallai tétele, a gráfparaméterek közti kapcsolatok, a definíciók.

4. Menger tétel pontdiszjunkt utakra két ponthalmaz között. A Menger tétel éldiszjunkt utakra. A Menger tételek két pont közti utakra. (Itt nem voltak bizonyítások, csak a fogalmakat kell tudni, illetve a tételek kimondását érteni.) (EB 12.2, KRS 2.9.6.) ABSZOLÚT MINIMUM: a fogalmak.

5. 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. csak a "pont"-os változatban, egy lemma gyakorlaton volt!). Kétszeres összefüggőség és két ponton/élen átmenő kör létezése. Dirac tétele (biz. nélkül), ellenpélda a Dirac tétel megfordítására (k hosszú kör). (KRS 2.9.7) ABSZOLÚT MINIMUM: a definíciók, szemléltetés példákon, a tételek kétszeres összefüggőségre.

6. Á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. ABSZOLÚT MINIMUM: minden. (anyag a honlapomon)

7. 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.!!!) ABSZOLÚT MINIMUM: a tükrözési elv, a +/-1 sorozatos megfogalmazás és az explicit képlet.

8. Rekurzió a Catalan-számokra. Catalan-számokra vezető nevezetes feladatok: konvex n-szög háromszögekre bontása, n tényezős szorzat zárójelezései, elég egy példánál tudni a rekurzió felírásának bizonyítását. (anyag a honlapomon, KRS 7.5, de ott MÁS a def.!!!) ABSZOLÚT MINIMUM: a rekurzió kimondása, és legalább egy feladat esetén a feladat megoldása a rekurzióval.

9. Ramsey tételei a teljes részgráf/üres részgráf megfogalmazásban, illetve a teljes gráf éleinek színezésével. Az R(k,l) Ramsey-szám definíciója. R(3,3) meghatározása, R(k,l)<=R(k-1,l)+R(k,l-1), ennek segítségével a binomiális együtthatós felső becslés. (A becslés általában nem éles, gyakorlaton volt: R(3,4)=9). Az Erdős féle alsó becslés (biz. csak az ötösért). (anyag a honlapomon, KRS 2.12.1, EB 4.1, kicsit más jelölés!!) ABSZOLÚT MINIMUM: a definíciók pontos értése, a rekurzió és a felső becslés.

10. 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 (itt kell a biz.), illetve a sok 3-as bizonyítás lemásolása (itt nem kell a biz.). (anyag a honlapomon, EB 4.4, 5.1) ABSZOLÚT MINIMUM: a fogalmak és a színösszevonás pontos értése.

11. 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 (biz. nélk.). r osztályú gráfok, a Turán-gráf. Az r osztályú gráfok között a Turán-gráf élszáma a legnagyobb (biz. csak az ötösért.) ABSZOLÚT MINIMUM: Mantel tétele és a Turán-gráf definíciója + a Turán tétel kimondása. (anyag a honlapomon, EB 10.1, KRS

12. 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): koordináta-geometria modulo p. (anyag a honlapomon, EB 10.3, LPV 14.1, 14.2 motivációt ad a geometriákhoz) ABSZOLÚT MINIMUM: a tételkimondások.

13. Halmazrendszerekre vonatkozó extremális kérdések: Sperner-rendszerek, Sperner tétele. A LYM (YBL M) egyenlőtlenség, a Sperner tétel biz. Bollobás tétele keresztben metsző halmazrendszerekről. Kapcsolat a Sperner tétellel. (EB 13.1, KRS 8.2) ABSZOLÚT MINIMUM: LYM (YBL M) egyenlőtlenség és az, hogy ebből hogyan következik a Sperner tétel + a definíciók.

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

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

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

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

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 többet annál, mint ami szükséges). A csak az ötöshöz szükséges részeket *-gal, a még ezen is túlmenő részeket **-gal jelöltem.

A vizsga menetéről ld. a TÁJÉKOZTATÓ-t (külön file).