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

2024 ôszi kurzus

Vizsgatételek

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). (A vizsgázás jogának (tehát az aláírás megszerzésének) feltétele, hogy a három legjobb kiszh legalább elégségesre sikerüljön, azaz (egyenként) elérje a rajta megszerezhetô pontszám legalább 40 százalékát.)

Elôadások rövid kivonata:

1. (szeptember 6.) : Hipergráfok fogalma, ekvivalens nézôpontok (gráfok általánosításai, halmazrendszerek, 0-1 sorozatok halmazai, kódok). Összefüggô és körmentes H hipergráfra az (|E|-1) mennyiségek összege az összes E élre |V(H)|-1. Ryser-sejtés; 1-faktorizálhatóság, Baranyai tétel. Sperner tétel kimondása.

Segédanyagok:

Lovász László: Kombinatorikai problémák és feladatok c. könyvében a fenti összefüggés a 13.1 feladat.

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

Baranyai tétel leírása a wikipedián.

2. (szeptember 13.) : Sperner tétel bizonyítása, LYM-egyenlôtlenség, Bollobás-egyenlôtlenség, Ahlswede-Zhang azonosság.

Segédanyagok: Sperner tétel bizonyítással a wikipedián.

LYM egyenlôtlenség bizonyítással a wikipedián.

Lovász László: Kombinatorikai problémák és feladatok c. könyvében a Bollobás-egyenlôtlenség (uniform esetre, az általános eset érvelése majdnem ugyanez) a 13.32 a) feladat.

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

3. (szeptember 20.) : Árnyékok, lexikografikus és kolexikografikus rendezés, természetes számok r-binomiális felírása. Az r-binomiális felírás létezése és egyértelmûsége, Kruskal-Katona tétel kimondásasa.

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

4. (szeptenber 27.) Eltolási operátor, Eltolási Lemma, KruskalüKatona tétel bizonyítása. Metszô rendszerek, Erdôs-Ko-Rado tétel és Daykin-féle (Kruskal-Katona tételt használó) bizonyítása.

5. (október 4.) Erdôs-Ko-Rado tétel Katona-féle (dupla leszámlálást használó) 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. A KG(5,2) gráf és a Petersen gráf izomorfiája. Borsuk-Ulam tétel legismertebb alakja (BU), valamint a Lyusternik-Shnirel'man változat 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.

Segédanyag: Matoušek könyve, melynek 2. fejezete innen letölthetô. Ez a fejezet tartalmazza a Borsuk-Ulam tétel különféle alakjait.

6. (október 11.) : Gale Lemma kimondása és a Lovász-Kneser tétel ezt felhasználó, Bárány féle bizonyítása. Lovász-Kneser tétel Greene féle bizonyítása, ami kikerüli a Gale Lemmát. Ezután igazoltuk a Gale Lemmát és 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, amire még visszatérünk legjözelebb.

Segédanyag: Matoušek könyvének 3.3 és 3.5 fejezete is innen letölthetô. Ezek tartalmazzák a fentieket.

7. (október 18.) : Felidéztük a múltkor belátott "erôs" Gale Lemmát, majd definiáltuk az SG(n,k) Schrijver gráfokat, kimondtuk és bebizonyítottuk Schrijver tételét. Ezután a Dolnyikov tétel és bizonyítása következett. A tétel kimondásához defináltuk a benne szereplô két új fogalmat, a "2-coloring deficiency"-t és az általánosított Kneser gráfokat. Azt is tisztáztuk, hogy hogyan következik a Dolnyikov tételbôl a Lovász-Kneser tétel.

Segédanyag: . A Schrijver tétel második állításának bizonyítása, megtalálható 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. A tétel elsô állításának bizonyítása, valamint a Dolnyikov tétellel kapcsolatos tudnivalók megtalálhatók a fent belinkelt Matoušek könyv letölthetô 3.4 és 3.5 fejezetében

8, (október 25.) : Lineáris algebrai módszerrel bizonyítható kombinatorikus tételek: Páratlanváros tétel, Párosváros tétel. E kettô megtalálható Freud Róbert Lineáris algebra címû könyvében itt. És egy harmadik: 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.) Ezután: Borsuk kérdése (ami "Borsuk-sejtés" néven vált ismertté). Kimondtuk az erre nemleges választ adó Kahn-Kalai tételt. A bizonyítás elôkészületeként megbeszéltük az abban majd használandó becslést, miszerint 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. Ennek a ténynek egy általánosabb, multinomiális együtthatókra vonatkozó változata is érvényes, az ezt kimondó általánosabb tétel bizonyítása megtalálható itt .

9, (november 8.) : 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.

10. (november 15.) 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. 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 az ezeket egyszerre általánosító Nešetřil-Rödl tétel kimondása. A bizonyítás elôkészületeként az uniform hipergráfokra vonatkozó "alap" Ramsey tétel kimondása.

11. (november 22.) Megkezdtük a Nešetřil-Rödl tétel bizonyítását. Igazoltuk az önmagában is fontos "alap" Ramsey tételt uniform hipergráfokra (amit használ a bizonyítás), utána pedig beláttunk két lemmát, amit használni fogunk a bizonyításhoz. Ezek Reinhard Diestel: Graph Theory c. könyvében 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.

12. (december 6.) 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.) Ezután Chvátal R(T,K_s) Ramsey számra vonatkozó tételének bizonyítását tárgyaltuk, (ld. mint Proposition 9.2.1 a Diestel könyv 287-288. oldalán.)