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

2023 ô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 5.) : 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.

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.

2. (szeptember 19.) : Sperner tétel, LYM egyenlôtlenség, Bollobás egyenlôtlenség. Véges halmaz részhalmazai rendszerének láncokra való felbontása.

Segédanyagok:

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

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

3. (szeptember 26.) : Ahlswede-Zhang azonosság. Árnyékok, lexikografikus és kolexikografikus rendezés, természetes számok r-binomiális felírása, ennek létezése. Kruskal-Katona tétel kimondása.

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

4. (október 3.) : Az r-binomiális felírás egyértelmûsége, Kruskal-Katona tétel 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. (október 10.) : 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. (október 17.) : 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á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. Gale Lemma kimondása és a Lovász-Kneser tétel ezt felhasználó, Bárány 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 (ld. még a következô linket is), melyben ez a bizonyítás is szerepel, ami innen letölthetô a 3.3 alfejezet részeként. (A Borsuk-Ulam tétel különféle alakjait tartalmazó 2. fejezet szintén letölthetô ugyanonnan.)

7. (október 24.) : Igazoltuk a Gale Lemmát. 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 két állítását, a fentiek alapján már bebizonyítottuk az egyiket, nevezetesen, hogy SG(n,k) kromatikus száma is n-2k+2. A Schrijver tétel másik, az SG(n,k) színkritikusságára vonatkozó állítása részletesebben már a következô héten kerül csak sorra. (Az ezen az elôadáson elhangzottak szintén megtalálhatóak a fentebb már belinkelt Matoušek könyv letölthetô 3.5 fejezetében.) Óra végén még megnéztük, hogy SG(2k,k) egyetlen él és SG(2k+1,k) egy 2k+1 hosszúságú páratlan kör, valamint lerajzoltuk SG(6,2)-t. Utóbbit a Klein kancsó négyszögeléseként is.

8. (október 31.) : 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. Dolnyikov tétel és bizonyítása. 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. (A Dolnyikov tétellel kapcsolatos tudnivalók szintén megtalálhatók a fent belinkelt Matoušek könyv letölthetô 3.4 fejezetében.)

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

10. (november 14.) : 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 .

11. (november 21.) 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.

12. (november 28.) A múltkor Graham válaszaként emlegetett tétel á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. Még csak elkezdtük a Nešetřil-Rödl tétel bizonyítását: ehhez elôször 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.

13. (december 5.) 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.) [Végezetül még szó volt a Hamming kódok egy meglepô alkalmazásáról.]