Halmazrendszerek (Matematikus MSc), 2021/2022 tavasz
Szerda 12:00-14:00, Kerékjártó terem
KÖVETELMÉNYEK
A kurzus tételhúzásos szóbeli vizsgával zárul a vizsgaidőszakban.
A tétel kidolgozása előtt beugróként ismertetni kell a tételben szereplő fogalmakat és kimondani a fő tételeket, segédanyagok használata nélkül.
Majd következik a tétel kidolgozása (bizonyítások stb.), ahol 10 percig bármilyen írott segédanyag olvasható (olvasás közben a jegyzetelés nem megengedett).
TEMATIKA / TÉTELSOR
Az írott segédanyagok többségét Hajnal Péter készítette, és az ő honlapjáról vannak linkelve.
1. Alaptételek I. Halmazrendszer és hipergráf fogalma, k-uniform halmazrendszerek.
Erdős—Ko—Rado-tétel metsző k-uniform halmazrendszerekről (5. tétel ITT).
Napraforgók, Erdős—Rado-tétel (1. tétel ITT).
2. Részbenrendezett halmazok. Láncok, antiláncok, láncfedések, antiláncfedések. Mirsky és Dilworth tételei (1. tétel ITT).
Gallai—Milgram-tétel.
3. Alaptételek II: Sperner-rendszerek. Sperner tétele antiláncokról, LYM-egyenlőtlenség (9. tétel ITT).
A Sperner-tétel alternatív bizonyítása láncfedéssel.
4. Vapnyik—Cservonyenkisz-dimenzió. Nyom. Vapnyik—Cservonyenkisz-dimenzó, Vapnyik—Cservonyenkisz-tétel
(3. tétel ITT). A shift operáció egy további alkalmazása: Bondy tételei.
5. Katona—Kruskal-tétel I. Halmazrendszer árnyéka. k-binom számrendszer, és a Katona—Kruskal-tétel erős alakja.
(segédanyag ITT, de a tételkimondást kicsit pontosítani kell, pl. a 6. tétel angol segédanyaga alapján).
Annak megmutatása, hogy a Katona—Kruskal-tételben az alsó becslés éles.
6. Katona—Kruskal-tétel II. A Katona—Kruskal-tétel Lovász-féle alakja. Shift operáció, és a Lovász-féle alak bizonyítása
(segédanyag ITT). Az Erdős—Ko—Rado-tétel levezetése a Katona—Kruskal-tételből.
7. Hipergráfok néhány paramétere. Párosítások, lefogó ponthalmazok. Tört-párosítások és tört-lefogások. A ν, ν*, τ és τ* paraméterek, és ezek kapcsolata
(segédanyag ITT).
Alapbecslések maximális fokszám és minimális élméret segítségével; reguláris uniform halmazrendszerek. Mohó lefogási algoritmus és analízise (Lovász tétele)
(segédanyag ITT).
8. "Két halmazrendszer" tételek. (segédanyag ITT)
Uniform τ-kritikus halmazrendszerek élszámbecslése. Bollobás és Lovász "két halmazrendszer" tételei.
9. Halmazrendszerek metszet feltételekkel. (segédanyag ITT)
Fisher-egyenlőtlenség. Frankl—Wilson-tétel, Ray-Chaudhuri—Wilson-tétel, moduláris változatok.
10. Halmazrendszerek metszet feltételekkel II. (segédanyag ITT)
Vektorok tenzorszorzata. Kahn—Kalai-tétel.
11. Halmazrendszerek színezése. (segédanyag ITT) Halmazrendszer jó csúcsszínezése, kromatikus szám. 2-színezhetőség (B tulajdonság).
k-uniform halmazrendszerek garantált 2-színezhetősége bizonyos élszám mellett (alsó és felső becslések, Pluhár András tétele).
Lovász lokális lemma kimondása.
A LLL alkalmazása k-uniform halmazrendszerek színezésére (a segédanyag utolsó tétele, ami már nem fért bele; de ez annyira
közvetlen alkalmazása a LLL-nak, hogy az LLL ismeretében ez egy egyszerű gyakorló feladat). A hiányzó számolások: ITT.
*** A VIZSGAANYAGON TÚL ***
+1. Ultraszűrők. Ultraszűrők (ld. 1-2. alfejezet).
Arrow tétele: a diktátortétel (prezentáció) +
egy bizonyítás (Ebben a Lemma 16 bizonyítása hibás:
Sv,ab nem teljesíti az egyhangúság tulajdonságot, így nem alkalmazható rá a Lemma 15. A hiba javításáért [és más szép ultraszűrő-alkalmazásokért] érdemes elolvasni
a hivatkozott Komjáth—Totik-cikket, ami legálisan elérhető az intézeti hálózatról.)
+2. Perfekt gráfok. A gyenge perfektgráf-tétel bizonyítása halmazrendszerekkel.
AJÁNLOTT IRODALOM, ONLINE SEGÉDANYAGOK
Hajnal Péter: Halmazrendszerek (Polygon Jegyzettár)
Hajnal Péter Halmazrendszerek kurzusának jegyzetei