GRÁFOK, HIPERGRÁFOK ÉS ALKALMAZÁSAIK - INFORMATIKUSOKNAK
2022 tavaszi kurzus
Elôadások:
1. (február 14.) : 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.
Segédanyag: Ryser sejtés leírása a wikipedián.
2. (február 21.) : Baranyai tétel bizonyítása.
3. (február 28.) : Sperner tétel, LYM-egyenlôtlenség, Bollobás-egyenlôtlenség, Ahlswede-Zhang azonosság kimondása.
4. (március 7.) : Ahlswede-Zhang azonosság bizonyítása. Láncokra való felbontás, Dilworth tétel, perfekt gráfok, ôsszehasonlítási gráfok perfektsége, Perfekt Gráf Tétel (PGT), Đilworth tétel és Mirsky tétel ekvivalenciája a PGT alapján.
Segédanyag: Az Ahlswede-Zhang azonosság bizonyítása megtalálható itt Rudolf Ahlswede és Zhen Zhang eredeti cikkében.
5. (március 21.) : Á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û.
6. (március 28.) : 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.
Segédanyag a Kruskal-Katona tételhez Bollobás Béla könyvének idevonatkozó néhány oldala. (Elforgatva olvasható jól.)
7. (április 5.) : 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 Greene féle bizonyítása. Igyekeztem hangsúlyozni a Lovász-Kneser tétel bizonyításának nagy hatását, ezzel kapcsolatosak az alábbi linkek: 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, melyben ez a bizonyítás is szerepel, ami innen letölthetô a 3.3 alfejezet részeként.
8. (április 12.) : 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. (Mindez szintén megtalálható a Matoušek könyv innen letölthetô 3.3-3.5 fejezetében. Belekezdtünk a "Lineáris algebrai módszerrel bizonyított kombinatorikus tételek" címmel illethetô részbe: Páratlanváros tétel, Párosváros tétel, egyelôre csak az elôbbit bizonyítottuk, utóbbit csak kimondtuk. Emellett elmondtam az ún. Borsuk-sejtést, jelezve, hogy annak (közel 60 év után megtalált) cáfolatát késôbb fogjuk látni, és az szintén egy lineáris algebrát használó kombinatorikai tételen alapul.
9. (április 26.) : Párosváros tétel bizonyítása, Graham-Pollak tétel bizonyítással. Kimondtuk a Borsuk kérdésére (ami "Borsuk-sejtés" néven vált ismertté) nemleges választ adó Kahn-Kalai tételt, jeleztem, hogy az A. Nilli néven megjelent egyszerûsített bizonyítást fogjuk tárgyalni és egyelôre ennek rövid vázlata hangzott el.
Segédanyag: A Páratlanváros és a Párosváros tétel bizonyítása megtalálható Freud Róbert Lineáris algebra címû könyvében itt, a Graham-Pollak tételé 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. (május 3.) : A Borsuk-"sejtés" cáfolatának múltkor már beharangozott A. Nilli féle egyszerûsített bizonyítását tárgyaltuk ezen az elôadáson.
Segédanyag: A fent említett bizonyítás összefoglalása megtalálható ebben a kézzel írott jegyzetben.
11. (május 10.) : Ramsey típusú tételek: alap Ramsey tétel gráfokra és hipergráfokra, Ramsey számok, azaz R(k), R(k,l) és általánosan R(k,c, (r_1,r_2,...,r_c)) definíciója. Erdôs és Hajnal kérdése, Graham válasza.
Segédanyag: Graham eredti (összesen 1 oldalas) cikke letölthetô innen
12. (május 17.): Nešetřil-Rödl tétel és bizonyítása: ehhez elôször beláttunk két lemmát (a 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). A teljes bizonyítás szerepel Reinhard Diestel "Graph Theory" c. könyvének 9. fejezete 295-300. oldalain.)
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 jegy megállapításához figyelembe vett teljes pontszám 30%-át (a maradék 70%-ot a szóbeli vizsga).