Elôadások:
1. (február 10.): Hipergráfok fogalma, ekvivalens nézôpontok (gráfok általánosításai, halmazrendszerek, 0-1 sorozatok halmazai, azaz kódok). Ryser-sejtés; 1-faktorizálhatóság, Baranyai tétel kimondása.
2. (február 17.) Baranyai tétel bizonyítása.
3. (február 21. (május 4-i elôadás helyett)) Sperner tétel, LYM-egyenlôtlenség, Bollobás-egyenlôtlenség, Ahlswede-Zhang azonosság.
4. (február 24.) Stabil párosítások; árnyékok (témájának kezdete): kolexikografikus rendezés.
5. (március 2.) Kruskal-Katona tétel.
6. (március 9.) Kruskal-Katona tétel bizonyítása végének ismételt összefoglalása, Eltolási Lemma biznyítása. Erdôs-Ko-Rado tétel Daykin-féle (Kruskal-Katona tételt használó) és Katona-féle (dupla leszámlálásos) bizonyítása. Kneser gráfok definíciója (jelölés: KG(n,k)). Az Erdôs-Ko-Rado tétel következményeként KG(n,k) függetlenségi számának megadása, valamint annak tisztázása, hogy a legkisebb paraméterpár, amire KG(n,k) érdekes az n=5, k=2 értékpár és KG(5,2) éppen a Petersen gráf.
7. (március 23, elsô online elôadás) Terv: Kneser 1955-bôl származó, 1978-ban Lovász által bizonyított sejtését fogjuk tárgyalni. Elég pontosan (bár kihagyásokkal) fogom követni az itt szereplô könyv tárgyalását. A belinkelt oldal alján szerepel a tartalomjegyzék és a számunkra fontos részek mind szabadon letölthetôk. Két ilyen van, de az egyikbôl csak keveset fogunk használni: A 3.3, 3.4, 3.5 alfejezetek egyben töthetôk le, ez tartalmazza az itt tárgyalandó anyagunk nagy részét. Egész kevésre szükségünk lesz a 2.1 alfejezetbôl is, ezért érdemes a csak egyben letölthetô 2. fejezetet is letölteni. (Postscript file-ok, remélem mindenki meg tudja nyitni.) (Ha szükséges: Link postscript-rôl pdf-re konvertáláshoz .)
Hasznos elôkészület: Ha a 3.3 alfejezet elejét a 3.3.2 Theorem kimondásáig bezárólag el tudjátok olvasni, az segítheti az óra követését. (Az elsô fél oldaltól senki ne ijedjen meg, itt az eredeti, kicsit nehézkesebb nyelven szerepel a probléma, de rögtön utána ott van a gráfos fordítás.)
A március 23-i, elsô online elôadás utólagos összefoglalása: Kneser-sejtés, Kneser gráf kromatikus számának felsô becslése, Borsuk-Ulam tétel két alakja (Matoušek könyvben (BU1a) és (LS-c), illetve (LS-o)), (LS-c) bizonyítása (BU1a)-ból, Lovász-Kneser tétel Greene féle bizonyítása.
Felvétel itt található. Greene az egyszerû bizonyításáért elnyerte Amerikában a diákokat kutatási eredményeikért díjazó Morgan prize-t. Erról itt olvasható egy rövid cikk.
8. (március 30, második online elôadás) Terv: A Lovász-Kneser tétel két általánosítását fogjuk tárgyalni. Ezek: Dolnyikov tétele és Schrijver tétele. Utóbbi elôkészítéseként megbeszéljük a Lovász-Kneser tétel Bárány-féle bizonyítását, amihez szükségünk lesz a Gale Lemma nevû állításra is.
Mindezeket a Matoušek könyv 3.4 és 3.5 alfejezetei tartalmazzák, amik a múltkor megjelölt letölthetô anyagban benne vannak. (A Dolnyikov tételnek csak az ott leírt elsô bizonyítását fogjuk tárgyalni.)
A március 30-i, elôadás utólagos összefoglalása: A fenti terveknek megfelelôen Dolnyikov tételét és Schrijver tételét tárgyaltuk bizonyításukkal együtt. (Schrijver tétele esetén a csúcs-színkritikusságot nem bizonyítottuk.) Utóbbihoz megbeszéltük a Lovász-Kneser tétel Bárány-féle bizonyítását, illetve a Gale Lemma bizonyítását. Mindez írásban elérhetô a Matoušek könyv 3.4. és 3.5 alfejezeteiben, ami a múltkor megjelölt letölthetô anyag része. (Schrijver eredeti cikke elérhetô ezen a helyen , annak 6. oldalán a Theorem 3 mondja ki a csúcs-színkritikusságot, a bizonyítást pedig a következô másfél oldal tartalmazza.)
9. (április 6, harmadik online elôadás) Terv: Éppen a Borsuk-Ulam tételt tartalmazó cikkben fogalmazta meg Borsuk a következô kérdést: Igaz-e, hogy az n dimenziós valós térben adott tetszôleges korlátos E halmaz feldarabolható n+1 olyan részre, melyek mindegyikének kisebb az átmérôje, mint E-nek? Meglepô módon erre a folytonos kérdésre a diszkrét matematika eszközeit bevetve született meg a válasz. Jeff Kahn és Gil Kalai adott ravasz ellenpéldát (nagy n-re) 1993-ban, vagyis 60 évvel azután, hogy Borsuk publikálta a kérdést. Az ô konstrukciójuknak egy A. Nilli neve alatt megjelent egyszerûsített változatával fogunk foglalkozni.
Az április 6-i, elôadás utólagos összefoglalása: A fent leírt Borsuk problémára adott nemleges választ néztük meg két változatban is: a Kahn-Kalai cikk (ez szabadon letöltehtô innen is) alapján, amiben a Frankl-Wilson tétel állítása van felhasználva, illetve A. Nilli egyszerûsített bizonyítása alapján, amiben a Frankl-Wilson tételt egy lemma helyettesíti, amit be is bizonyítottunk. Ennek a bizonyításnak érdekessége, hogy lineáris algebrai érvelést használ. E bizonyítás összefoglalása megtalálható itt . Mindkét érvelésben szükségünk volt arra, hogy az "n alatt a cn" binomiális együttható c<1/2 esetén exponenciálisan kisebb mint 2 n-edik hatványa. Ennek (illetve egy ennél valamivel általánosabb állításnak) a bizonyítása megtalálható itt .
10. (április 20, negyedik online elôadás) Terv: További nevezetes, lineáris algebrai módszerekkel bizonyítható kombinatorikai tételek: Páratlanváros tétel, Párosváros tétel, Graham-Pollak tétel.
Az április 20-i, elôadás utólagos összefoglalása: A fent említett három tételt beszéltük meg bizonyításukkal együtt. Az elsô kettôt Freud Róbert Lineáris algebra c. tankönyvének tárgyalását követve (a megfelelô oldalak elérhetôek itt ). A Graham-Pollak tétel bizonyításához Tverberg gondolatmenetét használtuk, amely Martin Aigner és Günter M. Ziegler "Proofs from THE BOOK" címû könyvében is szerepel (a megfelelô oldalak elérhetôek itt ). Megjegyzések az utóbbi könyvvel kapcsolatban: Megbeszéltük, hogy a cím Erdôs "A KÖNYV" fogalmára utal, a címlapon Erdôs kézírása látszik. Ezt illusztrálandó bejátszottam egy rövid részletet George Csicsery "N is a number" címû, Erdôs Pálról szóló filmjébôl. Ennek elsô kb. tíz perce megtalálható itt . (A bejátszott részlet 5:56-nál kezdôdik.) [Hat ilyen kb tíz perces részletben az egész film elérhetô online.]
11. (április 27, ötödik online elôadás) Terv: Két (illetve kettô plusz egy) nevezetes tétel a listaszínezési számról: Listaszínezési sejtés, Galvin tétele, Thomassen tétele valamint az annak élességét igazoló Voigt tétel.
Az április 27-i, elôadás utólagos összefoglalása: Kimondtuk a Listaszínezési sejtést, majd a fent említett kettô plusz egy tételt (Galvin, Thomassen, Voigt) beszéltük meg bizonyításukkal együtt. A Galvin tétel és a Thomassen tétel bizonyítása megtalálható Reinhard Diestel "Graph Theory" c. könyvében, aminek fôszövege szabadon elérhetô (a címre klikkelve bejövô weboldalon). Az órán is ezt a szöveget használtuk, mely a könyv ötödik fejezetében (az egyes fejezetek külön pdf fájlokban szerepelnek a megadott oldalon) található a 133-134. oldalon (Galvin tétel), illetve a 131-132. oldalon (Thomassen tétel). A Voigt konstrukciójához órán rajzolt (kicsit kusza és zsúfolt) szemléltetô ábrám megtekinthetô itt, illetve nyomtatott illusztrációja szerepel Aigner-Ziegler "Proofs from THE BOOK" c. könyvének ezen oldalain.
12. (május 4, hatodik online elôadás) Terv: Ramsey típusú tételek. Alapvetô gráfokra és hipergráfokra vonatkozó Ramsey tétel; Erdôs és Hajnal kérdése, Graham gráf, általánosítás és egyben indukált Ramsey tétel elôkészületei.
A május 4-i, elôadás utólagos összefoglalása: Alapvetô gráfokra és hipergráfokra vonatkozó Ramsey tétel bizonyítással, a megfelelô Ramsey számokra vonatkozó felsô korlátokat is bizonyítva. Chvátal tétele az R(T,K_s) Ramsey szám értékérôl. Erdôs és Hajnal kérdése, Graham gráf (ennek helyessége a gyakorlaton lesz feladat). Nešetřil-Rödl általános tételének felvezetése. [A fentiek elsô része megtalálható Bollobás Béla "Graph Theory - An Introductory Course" c. könyvének itt elérhetô oldalain. Nešetřil-Rödl általános tételét Reinhard Diestel "Graph Theory" c. könyvének 9. fejezete 295-300. oldalain leírtak szerint fogjuk tárgyalni. A fenti Chvátal tétel is szerepel ugyanebben a fejezetben a 287. oldalon (Proposition 9.2.1), illetve megtalálható a Bollobás könyv 107. oldalán is (Theorem 4).]
13. (május 11, hetedik online elôadás) Terv: Nešetřil-Rödl tétel bizonyítása.
A május 11-i, elôadás utólagos összefoglalása: A Nešetřil-Rödl tétel bizonyítását tárgyaltuk a Diestel könyvben leírt módon. [A mai elôadás anyaga Reinhard Diestel "Graph Theory" c. könyvének 9. fejezete 295-300. oldalain szerepel.]
14. (május 18, nyolcadik online elôadás) Terv: Tört kromatikus szám fogalma és fôbb tulajdonságai.
A május 18-i, elôadás utólagos összefoglalása: Bevezettük a tört (vagy szintén gyakran használt szôval: frakcionális) kromatikus szám fogalmát. Bevezetô példaként a Scheinermann-Ullman: Fractional Graph Theory könyv Bevezetôjében levô példát használtuk, ami az elôbbi linken elérhetô néhány oldal elején olvasható. Utána e paraméter tulajdonságairól volt szó ezen összefoglaló alapján. A csúcstranzitív gráfokra vonatkozó, a tört kromatikus számot megadó formula alapján kiszámítottuk a Kneser gráfok tört kromatikus számát és megállapítottuk, hogy ebbôl és a Lovász-Kneser tételbôl adódik, hogy a tört kromatikus szám és a kromatikus szám közötti hézag akármilyen nagy lehet.
Gyakorlatok:
A március 26-i gyakorlatot a múltkor feladott házi feladatok megbeszélésével fogjuk kezdeni. Emlékeztetôül: múltkor feladott házi feladatok .
A múltkor feladott házi feladatok megoldásokkal . (Ezeket megbeszéltük a március 26-i gyakorlaton.)
A március 26-i gyakorlaton feladott feladatok (Elsô kettôt megbeszéltük, harmadik és negyedik házi feladat maradt.)
A március 26-i gyakorlaton feladott házi feladatok
2. kiszh (Beküldendô április 2-ig.)
Április 9-i gyakorlat:
A március 26-i gyakorlaton feladott házi feladatok közül a megbeszéltek megoldásokkal . (Az egyik feladat negnaradt házi feladatnak, az itt nem szerepel.)
Az április 9-i gyakorlaton feladott (és legalább részben megbeszélt) feladatok (Második feladatnál a megbeszélt stratégia optimalitásának bizonyítása, házi feladat maradt.)
Az április 9-i gyakorlaton feladott házi feladatok
3. kiszh (Beküldendô április 16-ig.)
Április 23-i gyakorlat:
Az április 9-i gyakorlaton feladott házi feladatok közül a megbeszéltek megoldásokkal . (Az egyik feladat negnaradt házi feladatnak, az itt nem szerepel.)
Az április 23-i gyakorlaton feladott (és legalább részben megbeszélt) feladatok
Az április 23-i gyakorlaton feladott házi feladatok
4. kiszh (Beküldendô április 30-ig.)
Május 7-i gyakorlat:
Az április 23-i gyakorlaton feladott házi feladatok közül a megbeszéltek megoldásokkal . (Az egyik feladat negnaradt házi feladatnak, az itt nem szerepel.) A negyedik feladat megoldásához itt egy további rajz.
A május 7-i gyakorlaton feladott feladatok egyikét sem sikerüt az óra ideje alatt megoldani, ezek is a házi feladatok közé kerütek.
A május 7-i gyakorlaton feladott házi feladatok
5. kiszh (Beküldendô május 14-ig.)
Május 21-i gyakorlat:
A május 7-i gyakorlaton feladott házi feladatok megoldásokkal .
A május 21-i gyakorlaton feladott feladatok. (A harmadik feladatot órán nem beszéltük meg, ennek megoldása is szerepel az elôbbi fájl második oldalán. Azért így elválasztva a feladatoktól, hogy aki még gondolkodna rajta, megtehesse, hogy csak azután nézi meg, hogy ezt megtette.)
Az óra végén még a Ramsey elmélethez kapcsolódóan kicsit beszéltem a Szemerédi tételrôl, valamint ajánlottam megnézésre a Szemerédi Endrérôl szóló (Kepes András által készített) portréfilmet.
Egy további "handout": a Kruskal-Katona tételhez Bollobás Béla könyvének idevonatkozó néhány oldala. (Elforgatva olvasható jól.)
Ars poetica: A tárgy oktatásakor a fô célnak a tananyag megtanítását tekintem és abból indulok ki, hogy a hallgatóság célja is a tanulás, nem pedig pusztán a jegy megszerzése. (Gyorsan hozzáteszem: remek hallgatók vették fel a tárgyat, a gyakorlatokon szerzett tapasztalataim ezt az elképzelést alátámasztják.) Ennek megfelelôen a számonkérés hangulatát sem szeretném azzal mérgezni, hogy mindenféle ellenôrzô manôverbe bonyolódom. Tudom, hogy aki ki akarja játszani a szabályokat, az úgyis ki tudja, de azt remélem, hogy evvel senki nem kíván (vissza)élni. Kérek minden hallgatót, hogy járuljon hozzá, hogy e sokak által bizonyára naívnak tartott elképzelés jegyében lebonyolítva a vizsgákat, utólagosan se rontsa el annak emlékét semmiféle gyanakvás. Kérni fogom (hangsúlyozottan: kérni és nem "elôírni", amit nem is tudnék és nem is akarok), hogy aki teheti, az kapcsolja be a kameráját a vizsgája alatt, de ennek oka, nem valamilyen ellenôrzési szándék, hanem az, hogy sokkal kellemesebb és interaktívabb így egy beszélgetés. (A vizsgákról felvételt nem fogok készíteni.)
Elôre is köszönöm mindenkinek a megértô közremûködést, jó felkészülést és kellemes vizsgázást kívánok!
Konzultációk: június 2, 8, 15, 23. napokon 10 órai kezdettel Teams rendszeren keresztül. (Ha 10:30-kor nincsen jelen senki, akkor kilépek, egyébként a konzultáció addig tart, ameddig van kérdés, lehetôség szerint legfeljebb déli 12 óráig.)
Ha valakinek megkezdôdött a vizsgája, akkor ô elôször egy tételt kap (sorsolni fogom, hogy melyiket) a tételsorból, kezdetben errôl kell beszélnie. Ha kívánja, ez elôtt kap néhány (maximum 5) percet, hogy összeszedje a gondolatait, de azonnal bele is foghat a feleletbe. Ezután még a teljes anyagból fogok kérdéseket feltenni, illetve, mint fentebb jeleztem, esetleg (de nem feltétlenül) egyszerûbb, vagy a gyakorlatokon megbeszélt nehezebb feladatok is elôfordulhatnak.
Mindenkinek kellemes vizsgaidôszakot kívánok!
.png){kind=link}