Halmazrendszerek
VIZSGA, 2010 Tavasz
A kurzusról történő
beszámolás kétféle módon történhet:
-
Egy írásos vizsga. Ez 100 pontra lesz skálázva.
-
A vizsga nap előtt maximum egy héttel egy feladatot húz a hallgató.
A feladat megoldását vagy amire rájött
gondolkozása során azt leírva a vizsgára hozza.
A megoldását és a vizsgát is 50 pontra skálázva pontozom.
Az összpontszám a két pontszám összege.
A pontszámtól függően a jegy:
- 1: < =50 összpont
- 2: 50 < összpont < = 60
- 3: 60 < összpont < = 70
- 4: 70 < összpont < = 85
- 5: 85 < összpont
Tematika
Alapfogalmak:
Halmazrendszer, hipergráf, k-uniformitás, Steiner-rendszer, Sperner-rendszer,
f-vektor, részben rendezett halmazok, lánc, antilánc,
metsző halmazrendszer, napraforgó/Δ-rendszerek,
halmazrendszer nyoma, Vapnyik-Cservonyenkisz-dimenzió,
árnyék,
független élhalmazok, lefogó ponthalmazok, tört-párosítások, tört-lefogások
&tau*, &nu*,
mohó algoritmus "kicsi" lefogó ponthalmaz keresésére,
&tau -kritikusság,
Kőnig-tulajdonság,
totálisan unimoduláris mátrix,
totálisan unimoduláris halmazrendszer,
szelíd kör halmazrendszerben, normalitás,
perfekt gráfok,
halmazrendszer kromatikus száma, a sík/tér kromatikus száma,
egy kompakt ponthalmaz Borsuk-paramétere,
Ramsey-szám.
Tételek:
Steiner-rendszerekre vonatkozó oszthatósági feltételek.
Steiner-rendszerek elemi konstrukciója.
Steiner-rendszerek egy rekurzív definíciója.
Steiner-rendszerek alaptételének kimondása.
Sperner-tétel. LYM-egyenlőtlenség.
Dilworth-tétel.
Erdős-Ko-Rado-tétel.
Erdős-Rado-tétel.
Vapnyik-Cservonyenkisz-tétel valamelyik bizonyítása.
Katona-Kruskal-tétel kimondása (kétféle alakban).
A mohó algoritmus analízise.
Menger-tétel kimondása.
Lucchesi-Younger-tétel kimondása.
Normális hipergráfok jellemzésének kimondása.
Perfekt gráf tétel bizonyítása a normális
hipergráfok jellemzéséből.
Erdős két tétele k-uniform halmazrendszerek 2-színezhetőségéről
(Ha 2k-1-nél kevesebb élük van, akkor biztos 2-színezhetők.
Lehet k22k élük és közben nem 2-színezhetők.)
Pluhár András tétele.
Lovász Lokális lemmájának kimondása.
A lokális lemma alkalmazása halmazrendszerek 2-színezésére.
Fisher-egyenlőtlenség, Erdős-de Bruijn tétele,
nem uniform Fisher-egyenlőtlenség kimondása.
Utóbbi bizonyítása.
Ray-Chudhuri-Wilson tétel és
nem-uniform változatának kimondása.
A nem-uniform tétel bizonyítása.
Konstruktív leírása egy Ramsey gráfnak.
ω vagy α paraméterének becslése.
Mintavizsga
-
-
Definiálja mikor mondjuk, hogy egy halmazrendszer metsző.
-
Milyen sok éle lehet egy n elemű halmaz feletti, metsző halmazrendszernek?
Indokolja válaszát.
-
Mi a válasz, ha halmazrendszerünk ráadásul k-uniform?
-
Bizonyítsa be állítását.
-
-
Definiálja a törtlefogás és törtpárosítás fogalmát
és a hozzájuk kapcsolódó optimalizálási feladatokat.
-
Adja meg páratlan gráfkörök esetén a két paraméter értékét. Indokolja
is válaszát.
-
Írja le a mohó algoritmust kicsi lefogó ponthalmaz keresésére
-
Mondja ki és bizonyítsa be azt az állítást, ami az
algoritmus által kiszámolt lefogó ponthalmaz méretére
vonatkozik.
-
-
Definiálja egy halmazrendszer kromatikus számát.
-
Mondja ki azokat a tételeket, amik k-uniform halmazrendszerek élszámára
vonatkoztak, amennyiben nem 2-színezhetők.
-
Egyiket bizonyítsa is be.