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

2023 tavaszi kurzus

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. (Az elégséges szintet a nagyzárthelyin és a három legjobban sikerült kiszárthelyin külön-külön el kell érni.)

Elôadások rövid kivonata:

1. (február 28.) : 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 és a bizonyítás elôkészítése.

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

2. (március 7.) : Baranyai tétel bizonyításának befejezése; Sperner tétel, LYM-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.

3. (március 14.) : Láncokra való felbontás, Dilworth tétel, ôsszehasonlíthatósági gráfok perfektsége, Perfekt Gráf Tétel (PGT), Đilworth tétel és Mirsky tétel ekvivalenciája a PGT alapján. Árnyékok, lexikografikus és kolexikografikus rendezés, természetes számok r-binomiális felírása.

4. (március 21.): Az r-binomiális felírás létezése és egyértelmûsége, Kruskal-Katona tétel kimondásasa és bizonyítása (egyelôre az Eltolási Lemma bizonyításának részletei nélkül.

Segédanyag a Kruskal-Katona tételhez: Bollobás Béla könyvének idevonatkozó néhány oldala. (Elforgatva olvasható jól.)

5. (március 28.): Eltolási Lemma bizonyítása. Metszô rendszerek: Erdôs-Ko-Rado tétel és Daykin-féle (Kruskal-Katona tételt használó) bizonyítása, 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, Kneser gráf kromatikus számának felsô becslése, ami motiválja a Kneser sejtést. Lovász-Kneser tétel kimondása.

6. (április 4.) : Borsuk-Ulam tétel legismertebb alakja (BU), valamint a Lyusternik-Shnirel'man változatok zárt, nyílt és vegyesen zárt és nyílt halmazokra. Az LSc (Lyusternik-Shnirel'man zárt alak) bizonyítása a Borsuk-Ulam tétel BU alakjából. Lovász-Kneser tétel Greene féle bizonyítása. Dolnyikov tétel kimondása, ehhez az általánosított Kneser gráf és a cd_2 ("coloring definciency") paraméter bevezetése. Annak tisztázása, hogy a Lovász-Kneser tételben a kromatikus szám alsó becslése speciális esete a Dolnyikov tételnek. 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.

7. (április 18.) : Dolnyikov tétel bizonyítása. Gale Lemma kimondása és a Lovász-Kneser tétel ezt felhasználó, Bárány féle bizonyítása. Ezután igazoltuk a Gale Lemmát is. Tisztáztuk, hogy a bizonyítás egy kicsit többet bizonyít és ezt kihasználva a Lovász-Kneser tételnek is megkapjuk egy általánosítását, Schrijver tételét. Ennek kimondásához definiáltuk az SG(n,k) Schrijver gráfokat és kimondtuk a Schrijver tétel azon állítását, amit a fentiek alapján már be is bizonyítottunk, nevezetesen, hogy SG(n,k) kromatikus száma is n-2k+2. Óra végén jeleztem, hogy a Schrijver tételnek lesz egy másik, az SG(n,k) színkritikusságára vonatkozó állítása is, de ennek részletei már a következô héten kerülnek csak sorra. (Az ezen az elôadáson elhangzottak szintén megtalálhatóak a fentebb már belinkelt Matoušek könyv 3.3 fejezetében.)

8. (április 25.) : Schrijver tétel második állításának bizonyítása, mely 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. Két lineáris algebrai módszerrel bizonyított kombinatorikus tétel: Páratlanváros tétel, Párosváros tétel. Mindkettô megtalálható Freud Róbert Lineáris algebra címû könyvében itt.

9. (május 2.) : Kimondtuk a Borsuk kérdésére (ami "Borsuk-sejtés" néven vált ismertté) nemleges választ adó Kahn-Kalai tételt, majd a Borsuk-"sejtés" cáfolatának A. Nilli féle egyszerûsített bizonyítását tárgyaltuk.

Segédanyag: A fent említett bizonyítás összefoglalása megtalálható ebben a kézzel írott jegyzetben. Az egyik becsléshez felhasználtuk, 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. Említettem, hogy ez a becslés az exponenciális nagyságrendet tekintve éles és hogy általánosabb, multinomiális együtthatókra vonatkozó változata is érvényes. Ez utóbbi általánosabb tétel bizonyítása megtalálható itt .

10. (május 9.) : Graham-Pollak tétel (Tverbergtôl származó bizonyítással). Ez megtalálható Martin Aigner és Günter Ziegler Proofs from THE BOOK címû könyvében itt. (Ez a könyv magyarul is megjelent Bizonyítások a könyvböl címmel.) Ramsey típusú tételek: alapvetô Ramsey tétel gráfokra. Ramsey számok, ezek nehézsége, R(k,l), illetve R(k) becslései. 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. Chvátal R(T,K_s) Ramsey számra vonatkozó tételének kimondásával zártuk az órát.

11. (május 16.) : Chvátal R(T,K_s) Ramsey számra vonatkozó tételének bizonyítása. 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 kimondása. Még csak 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 egy lemmát és még csak kimondtunk egy másodikat, amit használni fogunk a bizonyításhoz. Ezek a Diestel: Graph Theory c. könyvben a 9.3.2 és 9.3.3 számú lemmák, amik közül a második a tétel páros gráfokra vonatkozó esetét igazolja (kicsit erôsebb formában). Az R(T,K_s) Ramsey számra vonatkozó tétel szintén megtalálható (bizonyítással együtt) ebben a könyvben mint 9.2.1 Proposition.

12. (május 23.): Folytattuk és 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.) Utána még röviden elmondtam a "Happy End Probléma" néven ismertté vált tételt. (Ehhez háttéranyag található pl. ezen a wikipedia oldalon -noha itt, azt hiszem tévesen, csak a négyszögekre vonatkozó esetet illetik a "Happy End Probléma" névvel. Egy jóval részletesebb leírás - ahol egyéb általunk is tárgyalt Ramsey elméleti tételek bizonyítása is megtalálaható - szerepel az innen letölthetô az uppsalai szakdolgozatban.)

13. (május 30.): 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. Ezután Chvátal és Erdôs tétele következett, mely bizonyítással együtt megtalálható a Diestel könyv 10. fejezetében mint Proposition 10.1.2. Végül mutattam egy rövid, Schrijver tanult tételén alapuló bizonyítást arra, hogy ha a 3n csúcsú G gráf egy Hamilton kör és n darab csúcsdiszjunkt háromszög éldiszjunkt uniója, akkor G függetlenségi száma n. (Valójában egy ilyen G 3-színezhetô, vagyis három, páronként diszjunkt n elemû független halmazt is tartalmaz. A tanult bizonyításból két diszjunkt n elemô független halmaz létezése adódik.) Ez a bizonyítás elolvasható ennek a cikknek a 4. fejezetében (ld. Theorem 4.4).