Kombinatorika előadás (Matematika BSc), 2023/2024 tavasz

Csütörtök 8:00-10:00, Grünwald Géza terem

KÖVETELMÉNYEK

Gyakorlatról legfeljebb 60 pontot lehet hozni, az előadásvizsgán maximum 40 pont szerezhető.

Az előadásvizsga egy rövid írásbeli beugróval kezdődik, mely átfogó módon teszteli a tananyag fogalmainak és tételeinek ismeretét (bizonyítások nélkül), akár példákon keresztül. Amennyiben a beugróban komoly hiányosságokra derül fény, az érdemjegy szóbeli vizsga nélkül elégtelen. A beugró után egy tételhúzásos szóbeli vizsga következik: A hallgató egy kombinatorika és egy gráfelmélet tételt ismertet szóban, írásbeli felkészülés után. (A tételhúzás után kijelölöm, hogy mely részeket kell majd jobban részletezni, és melyeket elegendő kevésbé.) A 40 pontból legalább 15 pontot el kell érni a kurzus teljesítéséhez (alapvető hiányosságok 0 pontot eredményeznek). E feltétel teljesülése esetén a vizsgán megszerzett pontszámhoz hozzáadódik a gyakorlatról hozott pontszám (legfeljebb 60 pont), és kialakul az érdemjegy:
  0 – 49:   elégtelen
50 – 62:   elégséges
63 – 75:   közepes
76 – 87:   jó
88 – 100: jeles

A félév folyamán pluszpontokat is lehet gyűjteni az előadás alatt tett érdemi hozzászólással/hibajelzéssel. A pluszpontok hozzáadódnak a fent kialakult összpontszámhoz. Továbbá a tételsorban szerepelnek olyan elemek is, amelyek ismerete pluszpontokat jelent a szóbeli vizsgán.

TEMATIKA / TÉTELSOR

A lila szín a nehezebb anyagrészeket jelöli, ezeket csak a jeles érdemjegyet megcélzó hallgatóktól kérdezhetem (a beugróban biztosan nem fognak szerepelni).
A zöld színű részek nem tartoznak a vizsgaanyaghoz: ha a törzsanyag jól ment (!), akkor ezen kiegészítő részek ismerete pluszpontot ér.

1. Alapok (prezentáció): A kombinatorika három alapelve (összeadási, szorzási, bijekciós). Bijekció. Egy (véges) halmaz elemszámának precíz definíciója. Skatulyaelv (példával, pl. gyakorlatról), általánosított skatulyaelv. Kettős leszámlálás (példával, akár későbbi előadásról / gyakorlatról is). Részhalmaz karakterisztikus vektora. Hatványhalmaz. Egy n elemű halmaz részhalmazainak száma. Páros/páratlan elemszámú részhalmazok száma.
2. Binomiális együtthatók (prezentáció): A binomiális együtthatók definíciója. A Pascal-háromszög és alaptulajdonságai (rekurzió a binomiális együtthatókra; szimmetria; egy sor elemeinek összege). Képlet az (nk) binomiális együtthatóra. Binomiális együtthatók összehasonlítása. Binomiális tétel. SZORGALMI: Binomiális együtthatók paritása. (Bizonyítás ITT [9.tétel], a Pascal-háromszög Sierpiński-háromszögszerű ,,paritástérképének'' magyarazáta pedig ITT.) Páros/páratlan elemösszegű k elemű részhalmazok (9. oldal, 4. feladat).
3. Multihalmazok (prezentáció): Multihalmazok szemléletes jelentése. Multihalmazok precíz definíciója + alapfogalmak (multihalmaz elemei, elemszáma, részmultihalmazai). Részmultihalmazok száma. Egy n elemű alaphalmaz feletti k elemű multihalmazok száma. ((nk)) mint bizonyos vektorok száma. Az ((nk)) számok generátorfüggvénye.
4. Sorbaállítások (prezentáció): Sorbaállítás definíciója. Egy n elemű halmaz sorbaállításainak száma. Stirling-formula (biz. nélkül). Multihalmaz sorbaállításai, és ezek száma. Trinomiális és multinomiális tétel. Inverzióban álló elempár. Inverziószám definíciója és gyors kiszámítási módja. Páros/páratlan permutációk definíciója inverziószámmal (a Diszkrét matematika kurzuson tanult definícióval való ekvivalencia bizonyítása itt: ITT). Az inverziótábla egy bijekció Sn és {0,...,n-1}×...×{0,1}×{0} között. SZORGALMI: Az i(n,k) számok definíciója és generátorfüggvénye.
5. Átrendezések (prezentáció): Átrendezés (permutáció) definíciója. Egy n elemű halmaz átrendezéseinek száma. Bijekciók száma két n elemű halmaz között. Ciklusok. Minden permutáció ciklusokra bomlik. Egy n elemű halmaz 1 ciklusból álló permutációinak száma. Az [nk] számok definíciója és generátorfüggvénye. Az [nk] számok generátorfüggvényének szép levezetése.
6. Logikai szita (prezentáció): A szita formula. Alkalmazás: Fixpont nélküli permutációk száma (elcserélt levelek problémája).
7 Polinomok, formális hatványsorok (prezentáció): Formális hatványsorok és polinomok definíciója. Alapműveletek (összeadás és szorzás). Formális hatványsorok műveleti tulajdonságai (nem kell betanulni; számolni kell tudni formális hatványsorokkal), többtényezős szorzat. Formális hatványsor fokszáma, osztás (az alaptétel bizonyítása nélkül), egész kitevős hatványozás. Az 1/(1-x) formális hatványsor. Az 1/(1-x)2 formális hatványsor. Átfedés más témakörökkel: Az 1/(1-x)n formális hatványsor. Binomiális, trinomiális és multinomiális tétel (ld. a 2. és 4. témakörök prezentációiban). SZORGALMI: Deriválás. Kompozíció. n-edik gyök, tört kitevőjű hatványok, Newton-formula (ld. Formális hatványsorok prezentáció vége).
8. Rekurziók I. (prezentáció): Rekurzióval definiált sorozatok (elég, ha példákat tudunk felírni). A Fibonacci-számok és Catalan-számok rekurzív definíciója. A Fibonacci-számok és Catalan-számok (egy) kombinatorikus jelentése. Catalan-számok zárt alakja (biz. nélkül). Lineáris rekurziók. Lineáris rekurziók alaptétele (biz. nélkül), és alkalmazása lineáris rekurziók megoldására. Kiegészítő olvasmány: Lineáris rekurziók középiskolás tárgyalása (avagy "honnan jön" a karakterisztikus polinom). SZORGALMI: Catalan-számok zárt alakjának elemi bizonyítása.
9. Rekurziók II. (prezentáció): Lineáris rekurziók megoldása generátorfüggvény-módszerrel (konkrét feladatot kell tudni megoldani): példa #1, példa #2. Fibonacci-számok zárt alakja. Kiegészítő segédanyag: Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása (és parciális törtekre bontás).
10. Gráfelméleti alapok (prezentáció): Egyszerű gráf, (általános) gráf definíciója; hurokél, párhuzamos élek. Csúcs fokszáma. Reguláris gráfok. Izolált csúcs. Fokszámtétel (a fokszámösszeg és az élszám kapcsolata). Irányított gráfok (informálisan), kifokok, befokok, fokszámtétel irányított gráfokra. Néhány speciális gráf: teljes gráf, út-gráf, kör-gráf. Egyszerű gráf komplementere. Gráfok izomorfiája. Csúcs- és élelhagyás. Részgráf; feszítő és feszített részgráf. Séta, vonal, út, kör. Összefüggőség definíciója. A sétával való, illetve az úttal való összekötöttség kapcsolata.
11. Euler-vonal (prezentáció) Euler-vonal definíciója (nyílt és zárt). Euler-tétel. A történelmi példa: Königsberg (ma Kalinyingrád) térképe Euler idejében, és a gráf. Érdekesség: Hamilton játéka.
12. Hamilton-út, Hamilton-kör (prezentáció): Hamilton-út, Hamilton-kör definíciója. Dirac-tétel. Ore-tétel. Egy (nem mindig alkalmazható) módszer a Hamilton-kör/út-mentesség igazolására (ld. következő prezentáció).
13. Komponenesek, fák (prezentáció): Az elérhetőség reláció, gráfok komponensei. Fák ekvivalens definíciói (hasznos minél többet ismerni, de elég annyi, amennyi előadáson előjött). Feszítőfák. Levelek. Ághajtás operáció, fák struktúratétele (fák jellemzése ághajtás operációkkal). A fa éleinek száma. Összefüggő és körmentes gráfok élszámbecslései. Erdők. Gyökeres fák és lerajzolásaik (a lerajzolhatóságot csak kimondani).
14. Csúcsszínezések (prezentáció): Jó színezés és kromatikus szám definíciója. Klikkek, független ponthalmazok, ω(G) és α(G) paraméterek. A χ(G) alsó becslése az ω(G) ill. α(G) paraméterek segítségével. Mohó algoritmus (YouTube-videó a CooSpace-en), kromatikus szám felső becslése a maximális fokszám segítségével (YouTube-videó a CooSpace-en). Páros gráfok definíciója. Páros gráfok jellemzése páratlan körökkel (csak kimondani). Fokszámösszeg egy páros gráf két színosztályában.
SZORGALMI: Nagy kromatikus számú háromszögmentes gráfok létezése (bizonyítás: lásd 3. konstrukció itt).
15. Síkgráfok (prezentáció): Síkgráfok definíciója. Térképszínezési probléma, négyszín-tétel (bizonyítás nélkül :). A két alappélda nem síkgráfokra. Gráfok felosztása. Kuratowski-tétel. Síkra rajzolt gráf tartományai, Euler-formula (bizonyítás csak jelesért).
16. Párosítások (prezentáció): Párosítások, teljes párosítások, ν(G) paraméter. Párosítások páros gráfokban: Kőnig-akadály (mit akadályoz meg, és miért; egy Kőnig-akadály hány párosítatlan pontot garantál A-ban). Kőnig—Hall-tétel (a nehéz irány bizonyítása nélkül), Kőnig—Frobenius-tétel. Egy alkalmazás: teljes párosítás létezése reguláris páros gráfokban. Párosítások általános gráfokban: Tutte-tétel kimondása (+ miért szükségesek a feltételek). Lefogó ponthalmazok, τ(G) paraméter. A ν(G) és τ(G) paraméterek kapcsolata, Kőnig tétele. Kiegészítő segédanyag: Az órai anyagnál bővebb jegyzet párosításokról (a kihagyott bizonyításokkal együtt).
17. Extremális gráfelmélet (prezentáció): Turán-gráfok. Turán-tétel (biz. nélkül). Mantel-tétel. SZORGALMI: A Turán-tétel bizonyítása.
18. Ramsey-elmélet (prezentáció): Ramsey-tétel (+ bizonyítás). Az R(k) Ramsey-szám definíciója. R(3) pontos értéke (a kapcsolódó középiskolás feladat megoldásával együtt). R(k) alsó és felső becslése (Erdős és Ramsey tételei).

SEGÉDANYAGOK

Hajnal Péter: KOMBINATORIKAI FOGALOMTÁR (a legtöbb elhangzott definíció benne van)
A fő segédanyag a korábbi előadó, Hajnal Péter internetes jegyzete a kurzushoz: 2019/2020-as tanév
A tanárszakos kurzushoz készült jegyzet kevesebb anyagot tartalmaz, viszont olvasmányosabb: 2014/2015-ös tanév

GRÁFELMÉLETI FOGALMAK KÉPEKBEN

Euler-vonal: #1 (zárt), #2 (zárt), #3 (nyílt).
Hamilton-út: #1, #2. Hamilton-kör: #1, #2, #3.
Komponensek: #1 (gráf 4 komponenssel), #2 (gráf 3 komponenssel), #3 (gráf 3 komponenssel).
Fa: #1, #2. Feszítőfa: #1. Gyökeres fa lerajzolása: #1 (gyökér: 'r'), #2 (gyökér: 'a').
Síkgráf duálisa: #1, #2, #3, #4. A duális gráf az eredeti gráf lerajzolásától is függ: #1.
Jó (csúcs)színezés: #1, #2. Térképszínezési probléma / négyszíntétel szemléltetése: #1, #2.
Párosítás: #1 (nem teljes), #2 (teljes), #3 (páros gráf egy párosítása), #4 (páros gráf egy A-t lefedő párosítása), #5 (páros gráf egy teljes párosítása).
Kőnig-akadály: #1, #2. Lefogó ponthalmaz: #1.
Turán-gráf: #1 (T13,4, T14,4, T13,2 és T14,3), #2 (T7,3).

A képek többségét más oldalakról linkeltem (az URL-ből kiolvasható/megkereshető a forrás).

AJÁNLOTT IRODALOM

Hajnal Péter: Összeszámlálási problémák (Polygon Jegyzettár)
Hajnal Péter: Gráfelmélet, II. kiadás (Polygon Jegyzettár)
Lovász László: Kombinatorikai problémák és feladatok (Typotex, ingyenesen olvasható az interneten)
Bóna Miklós: Introduction to Enumerative Combinatorics (McGraw-Hill)
Reinhard Diestel: Graph Theory (Springer-Verlag, ingyenesen olvasható az interneten)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)
Benny Sudakov: Graph Theory (internetes jegyzet)

HASZNOS LINKEK

The On-Line Encyclopedia of Integer Sequences
Online rekurzió megoldó
The book "generatingfunctionology"

Főoldal