GRÁFOK, HIPERGRÁFOK ÉS ALKALMAZÁSAIK - INFORMATIKUSOKNAK

2021 tavaszi online kurzus

Vizsgatételek (A vizsgáról további információk a lap alján találhatóak.)

Elôadások:

1. (február 9.): 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. A bizonyítás elokészületeként kimondtuk a Kerekítési Lemmát.

Segédanyag: Ryser sejtés leírása a wikipedián.

2. (február 16.): Baranyai tétel bizonyítása.

Segédanyag: Gyárfás András és Hraskó András "Felbontás faktorokra" címû írása itt megtalálható. Ez tartalmazza a Baranyai tétel bizonyítását, az elôadáson is pontosan az itt leírt gondolatmenetet követtük.

További linkek: Pár szót beszéltem Baranyai Zsoltról és a róla az Érintô folyóiratban megjelent megemlékezésrôl. Ehhez van belinkelve ez az "Esettanulmány", amit javasoltam elolvasni azoknak, akiknek kedve van Baranyai Zsoltról kicsit személyesebb benyomást szerezni, vagy egyszerûen csak jól szórakozni egy szellemes íráson (összesen 3 oldal). Maga a megemlékezés itt olvasható.

3. (február 23.): Sperner tétel, LYM-egyenlôtlenség, Bollobás-egyenlôtlenség, Ahlswede-Zhang azonosság.

Segédanyag: Az Ahlswede-Zhang azonosság bizonyítása megtalálható itt Rudolf Ahlswede és Zhen Zhang eredeti cikkében.

4. (március 2.): Árnyékok - Lokális LYM egyenlôtlenség, Kruskal-Katona tétel állítása és a bizonyítás kezdete. Az állítás kimondásához bevezettük a kolexikografikus rendezést (elôtte a lexikografikust is, amivel összehasonlítottuk). A bizonyítás elôkészületeként bevezettük a természetes számok r-binomiális felírását és megmutattuk, hogy ez mindig létezik és egyértelmû.

5. (március 9.): Kruskal-Katona tétel bizonyítása (ezen belül még szerepelt az ún Eltolási Lemma és bizonyítása). Metszô rendszerek: Erdôs-Ko-Rado tétel Daykin-féle (Kruskal-Katona tételt használó) bizonyítása.

6. (március 16.): Erdôs-Ko-Rado tétel Katona-féle (dupla leszámlálásos) bizonyítása. Kneser sejtés, 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. Kneser gráf kromatikus számának felsô becslése, ami motiválja a Kneser sejtést. Lovász-Kneser tétel (egyelôre csak kimondása), Borsuk-Ulam tétel két alakjának kimondása. Igyekeztem hangsúlyozni a Lovász-Kneser tétel bizonyításának nagy hatását, ezzel kapcsolatban az alábbi linkeken található írásokat mutattam: Michael de Longueville cikke a bizonyítás 25 éves évfordulójára, Joshua Greene egyszerûsített bizonyításával elnyert díjának híre, és Matoušek könyve,

7. (március 23.): Borsuk-Ulam tétel legismertebb alakjából beláttuk hogyan következik a Lyusternik-Shnirel'man féle gömbfedésekre vonatkozó alak zárt halmazokkal, illetve vázoltam, hogy ebbôl hogyan adódik a nyílt halmazos változat. Ezután: Lovász-Kneser tétel Greene féle bizonyítása, Gale Lemma, ebbôl a Lovász-Kneser tétel Bárány féle bizonyítása, Gale Lemma bizonyítása. Mindez megtalálható a Matoušek könyv innen letölthetô 3.3-3.5 fejezetében, illetve a Borsuk-Ulam tételre vonatkozó részek a szintén letölthetô 2. fejezetben. Mutattam egy rövid interjú részletet, ahol Lovász László a Kneser sejtés bizonyításának történetérôl mond egy pár szót. Ez a 2011-ben készült interjú itt található, ebben a kérdezô éppen az az Avi Wigderson, akivel Lovász László közösen nyerte el a 2021-es Abel-díjat, melyet éppen a múlt heti elôadást követô napon jelentettek be. (Maga a bejelentés itt megnézhetô.)

8. (március 30.): Schrijver gráfok definíciója, Schrijver tétele, ennek bizonyítása. (A tétel elsô állításának bizonyításához explicit kimondtuk a Gale Lemma erôsebb alakját - a múltkori bizonyítás valójában ezt adta.) Általános Kneser gráf és hipergráfok cd_2 paraméterének definíciója, Dolnyikov tétele. A bizonyítás elôtt beláttuk azt is, hogy utóbbi általánosítja a Lovász-Kneser tételt. (Mindezek - a Schrijver tétel második állítása bizonyítását leszámítva - szintén megtalálhatók a Matoušek könyv innen letölthetô 3.3-3.5 fejezetében. A Schrijver tétel második állításának bizonyítása elolvasható Schrijver eredeti cikkében, ami 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 13.): Lineáris algebrai módszerrel bizonyított kombinatorikus tételek. Páratlanváros tétel, Párosváros tétel, Graham-Pollak tétel (Tverbergtôl származó bizonyítással). Az elôbbi kettô megtalálható Freud Róbert Lineáris algebra címû könyvében itt, a harmadik pedig Martin Aigner és Günter Ziegler Proofs from THE BOOK címû könyvében itt. (Utóbbi könyv magyarul is megjelent Bizonyítások a könyvböl címmel.)

10. (április 20.): Borsuk "sejtés" (valójában kérdés) néven volt ismert, hogy vajon 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, 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át ismertettem. (A bizonyítás összefoglalása megtalálható ebben a kézzel írott jegyzetben.)

11. (április 27.): Elôadás elején mutattam egy rövid bizonyítást arra a múltkor felhasznált tényre, hogy az olyan n hosszú 0-1 sorozatok száma, amikben pn 1-es szerepel valamilyen 0 és 1 közötti p értékre felülrôl becsülhetô 2-nek nh(p) kitevôjû hatványával, ahol h(p) a bináris entrópiafüggvény. Ezután Ramsey típusú tételekkel foglalkoztunk: alapvetô Ramsey tétel gráfokra, Erdôs és Hajnal kérdése arról, hogy megadható-e 6-nál kisebb klikkszámú gráf, aminek minden 2-élszínezésében lesz egyszínû háromszög, Graham válasza, ennek általánosítása, indukált Ramsey tétel, illetve a mindezeket egyszerre általánosító Nešetřil-Rödl tétel - utóbbit még csak kimondtuk, a bizonyítására visszatérünk. Most Chvátal R(T,K_s) Ramsey számra vonatkozó tételének bizonyításával zártuk az órát. (Ld. a következô elôadásnál hivatkozott Diestel könyvben Proposition 9.2.1-ként.)

12. (május 4.): Belekezdtünk a Nešetřil-Rödl tétel bizonyításába: ehhez elôször igazoltuk az önmagában is fontos "alap" Ramsey tételt uniform hipergráfokra (amit majd használ a bizonyítás), utána pedig beláttunk két lemmát (a fentebb már belinkelt Diestel könyvben ezek a 9.3.2 és 9.3.3 számú lemmák), amikbôl a második a tétel páros gráfokra vonatkozó esetét igazolja (kicsit erôsebb formában). Innen a befejezést a jövô heti elôadáson fogjuk megbeszélni. Az óra végén még meséltem a számelméleti jellegû Ramsey tételekrôl és ennek kapcsán Szemerédi híres tételérôl. Evvel kapcsolatban ajánlottam a youtube-on megnézhetô, Szemerédi Endrérôl szóló kb. félórás, Kepes András által készített Rend a káoszban címû filmet, aminek két rövid részletét bejátszottam ízelítôül.

13. (május 11.): Befejeztük a Nešetřil-Rödl tétel bizonyítását. (Még egyszer a link: a bizonyítás szerepel Reinhard Diestel "Graph Theory" c. könyvének 9. fejezete 295-300. oldalain.) Ezután még Chvátal "Art gallery tételét" tárgyaltuk (úgy, ahogyan Aigner és Ziegler Bizonyítások a KÖNYVbôl címû könyvében szerepel, melybôl a megfelelô részletet ld. itt. Az óra végén még lejátszottam egy pár perces részletet Erdôs Pál gólyavári elôadásából.

Gyakorlat:

A február 11-i gyakorlaton a február 25-i gyakorlatra feladott házi feladatok.

A február 25-i gyakorlaton a múltkor feladott házi feladatok megoldásán kívül ezeknek a feladatoknak a megoldását beszéltük meg.

A február 25-i gyakorlaton a március 11-i gyakorlatra feladott házi feladatok.

A március 11-i gyakorlaton a múltkor feladott házi feladatok megoldásán kívül ennek a feladatnak a megoldását beszéltük meg (valamint egy másik feladat kapcsán megtippeltük, hogy mely Sperner rendszerek esetén lesz egyenlôség a LYM egyenlôtlenségben, így a megfelelô feladat már így vált házi feladattá).

A március 11-i gyakorlaton a március 25-i gyakorlatra feladott házi feladatok.

A március 25-i gyakorlaton a múltkor feladott házi feladatok közül megbeszéltük az elsôt és a harmadikat, a másodikat eltettük további házi feladatnak. Ezután a stabil párosításokról beszéltünk, megbeszéltük a Gale-Shapley tételt bizonyító algoritmust és azt is, hogy ezt melyik irányból célszerû futtatni és miért. A múltkorról eltett házi feladat mellett még egy további házi feladatot adtam, ezen kicsit gondolkoztunk még az óra utolsó perceiben és a megoldás elsô lépéseit megtettük.

A március 25-i gyakorlaton az április 8-i gyakorlatra feladott házi feladatok.

Az április 8-i gyakorlaton a múltkor feladott házi feladatok közül megbeszéltük a másodikat, az elsôt továbbra is eltettük házi feladatnak. Ezután még ezeket a feladatokat sikerült megoldani az órán.

Az április 8-i gyakorlaton az április 22-i gyakorlatra feladott házi feladatok.

Az április 22-i gyakorlaton a múltkor feladott három házi feladat megoldását beszéltük meg, majd új elméleti anyagként bevezettük a listaszínezési szám (jele ch(G), az angol choice number elnevezésbôl) fogalmát, megbeszéltük (az elsô pillanatra talán meglepô) tényt, hogy ch(G)-nek mindig alsó korlátja a kromatikus szám és szigorú egyenlôtlenség olyannyira lehetséges, hogy még egy páros gráf choice number-e is lehet akármilyen nagy. (Erre mutattam egy bizonyítást.) Szerepelt még a fogalmat ihletô Dinitz probléma, a máig bizonyítatlan Listaszínezési sejtés, illetve kimondtuk Galvin tételét, ami ennek speciélis esete. Szintén kimondtuk a síkgráfok listaszínezésére vonatkozó Thomassen és Voigt tételeket.

Az április 22-i gyakorlaton a május 6-i gyakorlatra feladott házi feladatok.

A május 6-i gyakorlaton a múltkor feladott két házi feladat megoldását beszéltük meg, majd elmondtam a Galvin tétel bizonyítását. Ez a bizonyítás megtalálható Reinhard Diestel "Graph Theory" c. könyvében, aminek fôszövege szabadon elérhetô (a címre klikkelve bejövô weboldalon). A Galvin tétel 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. Utána még ennek a két feladatnak a megoldásával foglalkoztunk. Az óra végén beszéltünk még egy kicsit a vizsgáról is.

Számonkérések: A tárgy szóbeli vizsgával zárul, melynek eredményébe beleszámít a félév közben írt kiszh-k eredménye.

A félév során öt kiszárthelyit írunk, ezek közül a három legjobbnak az eredményét veszem figyelembe a vizsgán: ezek eredménye adja a vizsgán megszerezhetô teljes pontszám 20%-át.

Kiszh-k: A kiszh-kat a következôk szerint írjuk (kivéve ha valamilyen központi szabályozás ezt idô közben fölülírja, de ennek kicsi a valószínûsége). Az öt kiszh a 3., 5., 7., 9., 11. héten a gyakorlat napján, tehát csütörtökön kerül kiküldésre és az elkövetkezô két napban mindenki önállóan írhatja meg egy erre a célra kiválasztott 25 perces idôsávban Ennek lejárta után a dolgozatot (lehetôleg beszkennelve, ezt lehet mobiltelefonnal is) elküldi nekem, a beérkezési határidô az adott héten szombat éjfél. (Az elsô gyakorlaton részletesen beszéltünk arról, hogy ez a rendszer bizalmon alapul, mindenkit kérek, de azt remélem, hogy ebben a körben ezt fölösleges túlságosan hangsúlyozni, hogy ne adjon okot arra, hogy ez a megelôlegezett bizalom meginoghasson. Ezzel mindannyian csak nyerhetünk: jobb a légkör és a kiszh-k lebonyolítása is lényegesen egyszerûbb, mint bármilyen rabló-pandúr játékra emlékeztetô módon. Én alapesetben nem is kívánok foglalkozni annak lehetôségével, hogy a szabályok kijátszhatók. Természetesen azok, de abból szeretnék kiindulni, hogy mindenki tanulni akar, az én feladatom pedig a tananyag átadása, nem pedig ilyen-olyan csalási kísérletek leleplezése. A kiszh-k elsôdleges célja sem a számonkérés, hanem annak motiválása, hogy mindenki kövesse a tananyagot félév közben. Emiatt azt kérem, hogy ha valaki akár maximális pontszámmal megírja az elsô három kiszh-t, ha teheti - pl. betegség nem akadályozza benne - akkor is írja meg a hátralevô kettôt is. A kiszh-k egyébként három kérdésbôl fognak állni, ebbôl kettô valamilyen elméleti tudnivalóra kérdez rá, pl. egy tanult tétel kimondását kéri, egy pedig egyszerûbb, tehát a rendelkezésre álló rövid idô alatt is megoldható feladat.)

VIZSGATÉTELSOR

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

A vizsgáról: A vizsgaidôszakban (online) szóbeli vizsga lesz, amibe 20% súllyal beleszámít a félév során írt öt kiszh közül a legjobb háromon nyújtott teljesítmény. Magán a vizsgán egy tételsorból kap mindenki kérdést, egy tételrôl kell majd alaposabban beszélni, de a többibe is belekérdezek. Egyszerû feladatok, illetve akár a gyakorlatokon megbeszélt nehezebb feladatok is elôfordulhatnak.

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

Vizsgaidôpontok: május 26., június 2., 9. napokon 10 órai kezdettel a Teams rendszeren. (Jelentkezés a szokott módon a Neptunban lehetséges.)

Konzultációk: május 25., június 1., 8. napokon 10 órai kezdettel Teams rendszeren keresztül - csatlakozáshoz az eddigi elôadáslink használható. (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.)

A vizsga menete: A vizsga kezdetekor, tehát 10:00-kor kérem, hogy minden aznapi vizsgázó lépjen be a rendszerbe és csatlakozzon a "Vizsga" nevû meetinghez (aminek a linkjét a Teams csoportban látnia kell, de emailben is elküldtem), ott megbeszélünk egy vizsgázási sorrendet. Ez alapértelmezésben ábécé szerinti, de indokolt esetben lehet cserélni. Ezután a vizsga egyesével zajlik, a következô vizsgázóval mindig a sorrend rögzítésekor megbeszélt idôben lépek kapcsolatba (esetleges csúszás esetén igyekszem email-ben értesíteni, de remélem, hogy nem lesz erre szükség).

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!