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. (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. 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)

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). (KRS 2.9.2., 2.9.3.)

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

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)

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. (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.!!!)

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. (anyag a honlapomon, KRS 7.5, de ott MÁS a def.!!!)

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) Ransey-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. (anyag a honlapomon, KRS 2.12.1, EB 4.1, kicsit más jelölé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, illetve a sok 3-as bizonyítás lemásolása. Ramsey tétele r-esek színezéséről, az Erdős-Szekeres tétel nagy konvex sokszög létezéséről (ezek mind biz. nélk.) (anyag a honlapomon, EB 4.4, 5.1)

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. 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. (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)

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

14. A LYM (YBL M) egyenlőtlenség, a Sperner tétel második biz. Bollobás tétele keresztben metsző halmazrendszerekről. Kapcsolat a Sperner tétellel. (EB 13.1, KRS 8.2) Erdős-Ko-Rado tétele. (biz. nélk.) (EB 13.1, KRS 8.1)

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

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 picit többet annál, mint ami szükséges).

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