Tárgy neve: Kombinatorika ea. (BSc)

Tanszék: Halmazelmélet és Matematikai Logika Tanszék

Tematika:
Kombinatorikus alapelvek. Skatulya-elv, kettős leszámlálás. Részhalmazok összeszámlálása, k-elemű részhalmazok összeszámlálása, Pascal-háromszög. Binomiális tétel. Polinomok és a kombinatorika kapcsolata. Multihalmazok. Formális hatványsorok. Multihalmazok sorbaállításai. Trinomiális és multinomiális tétel. Sorbaállítások, inverziók és ezekkel kapcsolatos összeszámlálási feladatok. Átrendezések/permutációk, ciklusok és ezekkel kapcsolatos összeszámlálási feladatok. Szita formula és alkalmazásai. Rekurzíven leírt sorozatok. Fibonacci-számok és lineáris rekurzió. Catalan-számok. Gráfok fogalma, fokszám fogalma, példák. Sétálás gráfokban. Összefüggőség. Vonalak. Euler-vonal, Euler tétele. Utak, körök, Hamilton-út, Hamilton-kör. Dirac tétele. Gráfok komponensei, fák. Gráfok színezései. Páros gráfok. Mohó színezések. Térképszínezési probléma. Gráfok nagy kromatikus számmal, de nagy klikkek nélkül. Síkgráfok fogalma. Példák nem síkgráfokra. Kuratowski tételének kimondása. Hatszín-tétel. Párosítások gráfokban. Gráfok lefogása. Kőnig-tétel. A Tutte-akadály fogalma és Tutte-tétel kimondása. Klikkek. Mantel-tétel. Turán-gráfok és a Turán-tétel. Az extremális kombinatorika alapkérdése. R(3) értéke. Ramsey-tétel.

Előadás kódja: MBNK51E, óraszám: 2, kredit: 6