Halmazrendszerek speciálkollégium, Hajnal Péter XI. 11. (3 óra)

Vapnyik—Cservonyenkisz-dimenzió geometriai alkalmazásai: ϵ-hálók

Vapnyik—Cservonyenkisz-dimenzió geometriai alkalmazásai: illeszkedések számolása

Halmazrendszerek színezése

Definíció: Halmazrendszerek jó-színezése, kromatikus száma.

Lemma: Legyen H egy r-uniform halmazrendszer. Ha |H| ≤ 2^{r−1}, akkor χ(H) ≤ 2.

Bizonyítás: Egyszerű véletlen módszer.

⋆

Mennyire éles a fenti becslés. Hány r-elemű él adható V -n, hogy a kapott halmazrendszer ne legyen 2-színezhető? Tudjuk, hogy több mint 2^{r−1}. Esetleg jóval több? A kérdés egy lefogási feladattal ekvivalens:

Legyen H_{V,k} a következő halmazrendszer: Pontok: V alaphalmaz r-esei. Élek: V minden 2-színezéséhez egy élet rendelünk, azon k-asok halmazát, amelyek monokromatikusak leszenk. Egy nem 2-színezhető runiform halmazrendszer V felett pontosan a lefogó ponthalmazoknak felel meg. V -t (|V |-t) úgy kellene megválasztani, hogy τ(H_{V,k}) minél kisebb legyen.

τ^{∗} könnyen becsülhető. Ha tudjuk, hogy τ és τ^{∗} ”közel van egymáshoz”, akkor készen vagyunk.

Részletek kidolgozása jóvő órán.