GRÁFOK, HIPERGRÁFOK ÉS ALKALMAZÁSAIK - MATEMATIKUSOKNAK
2021 tavaszi online kurzus
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. [A fenti Ramsey típusú eredmények 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).]
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.
Gyakorlatok:
1. (február 8.): A Diaconis's Mind reading game néven is ismert bûvésztrükkel ismerkedtünk meg és tisztáztuk annak matematikai hátterét, az ún. deBruijn sorozatok létezését. Vagyis azt, hogy 16 db 0 és 16 db 1-es (de a 16 helyébe tetszôleges kettôhatvány írható) sorbarakható (pontosabban "körberakható") úgy, hogy az összesen 32 ciklikusan szomszédos bitekbol álló 5 hosszúságú sorozatok között mind a 32 lehetséges öt hosszú bitsorozat pontosan egyszer forduljon elô. Ennek bizonyítása az Euler körök létezésérôl szóló Euler tétel irányított változatán alapul, együtt megtaláltuk ezt a bizonyítást.
A fentiekkel kapcsolatban belenéztünk az alábbi videókba: Itt a kártyatrükk elmesélve hangzik el (32 helyett 16 lappal) 0:56 és 1:45 között. Megnéztük Persi Diaconis egy elôadása részletét is érdekességképpen, a 8:33-tól 10:32-ig terjedô részt láttuk ebbôl a felvételbôl. Ehhez kapcsolódik ez a régebbi videó, aminek az 1:41 - 2:39 részét megtekintve kis izelítôt kaptunk Diaconis bûvészi múltjából.
Óra végén feladtam még egy innen letölthetô házi feladatot.
2. (február 15.): Az órán megbeszélt feladatok ezek voltak.
Innen pedig letölthetôk az új házi feladatok,
3. (február 22.): Megbeszéltük a házi feladatok megoldásait, majd bevezettük az ún. WUM kódokat és beszélgettünk az ezzel kapcsolatban feladott, végül házi feladatnak megmaradt feladatról. A gyakorlat végén jeleztem, hogy (az elôzetesen megbeszéltek szerint) utána kiküldöm az elsô kiszh-t, melynek beküldési határideje szerda éjfél.
Az új házi feladatok innen tölthetôk le.
4. (március 1.): Megbeszéltük az elsô (a WUM kódos) házi feladat megoldását, majd az ezen témakört folytató itt látható két feladatot.
Az új házi feladatok innen tölthetôk le.
5. (március 8.): Megbeszéltük az elsô két házi feladat megoldását, a harmadik továbbra is megmaradt házi feladatnak. Ezután még két feladattal foglalkoztunk, az egyik szintén házi feladat maradt, a másik itt látható ezt sikerült megoldani.
Az új házi feladatok innen tölthetôk le.
6. (március 22.): Most is megbeszéltük az elsô két házi feladat megoldását és a harmadik továbbra is megmaradt házi feladatnak. Egy további feladatot oldottunk meg a gyakorlat ideje alatt, ez itt látható, két másik megmaradt házi feladatnak.
Az új házi feladatok innen tölthetôk le.
7. (március 29.): Megbeszéltük az elsô és a harmadik házi feladat megoldását, a másodikkal kapcsolatoban pedig az elindulást, de utóbbi megmaradt továbbra is házi feladatnak. Ezután eyg olyan anyagrészt tárgyaltunk, ami az informatikus társaságnál nem szerepel, ezért a gyakorlaton került sorra. Ez a Lovász Local Lemma nevû híres eredmény, ami a valószínûségszámítási módszer fontos eszköze. A valószínûségszámítási módszerrôl a társaság egy része tanult a Kombinatorika és gráfelmélet 2 tárgy keretében, de ezt nem mindenki hallgatta, ezért röviden ennek mibenlétét is összefoglaltuk. (A Lovász Local Lemmáról elhangzottak összefoglalása megtalálható ebben a kézzel írott jegyzetben.
Az új házi feladatok innen tölthetôk le.
8. (április 12.): Megbeszéltük a négy házi feladat megoldását. de nem jutottunk el a megoldásukig (az elsô kettôre valami elindulást azért megbeszéltünk, de ezt nem ismerve is érdemes gondolkodni rajtuk, illetve az elindulási ötlet megkereshetô a felvételen, ha valaki nem volt ott), ezek házi feladatok maradtak.
Az új házi feladatok innen tölthetôk le.
9. (április 19.): Megbeszéltük a három házi feladat megoldását. Ezután még két feladattal foglalkoztunk, az elsôre megszületett a megoldás, a második házi feladat maradt, Az elsô feladatot ld. itt.
Az új házi feladat innen tölthetô le.
10. (április 26.): Megbeszéltük a házi feladat megoldását, majd az itt olvasható feladatot oldottuk meg. Elkezdtünk foglalkozni ennek nehezebb változatával is, amikor három helyett hét játékos van. Ez végül házi feladat maradt, de vele kapcsolatban röviden beszéltünk egy fontos kódkonstrukcióról - ez egy segítség, ezért nem írom ide milyen kódról van szó, hogy aki inkább maga találná ki, megtehesse - ugyanakkor bárki a csoportból megtalálhatja a felvételen.
Az új házi feladatok innen tölthetôk le.
11. (május 3.): Megbeszéltük a második házi feladat megoldását, az elsôhöz pedig egy elindulást, és így eltettük a következô hétre, majd az itt olvasható feladatot oldottuk meg.
Az új házi feladatok innen tölthetôk le.
12. (május 10.): Megbeszéltük a három házi feladat megoldását, majd az itt olvasható két feladattal foglalkoztunk még. Az elsôt megoldottuk, a másodikra rövid idô maradt csak, de elhagnzott a megoldás egyik fô gondolata.
Számonkérések: A tárgy félévközi jeggyel zárul, ami egy nagyzh és öt kiszh eredményébôl alakul ki. Az öt kiszárthelyi közül a három legjobbnak az eredményét veszem figyelembe, ez adja a jegy 40, az egy nagyzárthelyi pedig a 60 százaléká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 hétfô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 szerda é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.)
Nagyzh: Amennyiben rajtam múlik (itt kicsit nagyobb az esélye, hogy valamlyen központi szabályozás megköti a kezem), akkor ezt is hasonló szellemben fogjuk lebonyolítani, mint a kiszh-kat, csak értelemszerûen hosszabb (várhatóan 120 perces) megengedett munkaidôvel. A tervezett idôpont pedig a tizedik oktatási hét.
Update: A nagyzh-t az április 19-ével kezdôdô héten írjuk a kiszh-kéval hasonló rendszerben. A zárthelyit hétfôn fogom kiküldeni. A megírásra 120 perc fordítható a határidôt megelôzô szabadon választott idôben. A határidô csütörtök éjfél, de megírás után kéretik a dolgozatot rövid idôn belül beküldeni. További tudnivalókat ld. a neptun rendszeren keresztül elküldött emailben.