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

Vapnyik—Cservonyenkisz-dimenzió

Definíció: H halmazrendszer V felett, U ⊆ V. U által feszített részhalmzarendszer (megszorítás H|_{U}), U által feszített parciális részhalmzarendszer. Definíció: U ⊆ V zsúfolt, ha H|_{U} = 2^{U}. Definíció: dim_{V C}(H). Példa: V = ^{2}, H: konvex k-szögek. Példa: V = ^{d}, H: félterek. Példa: V = ^{d}, H: gömbök. Tétel: (Vapnyik—Chervonyenkisz, Shelah, Perles, Sauer) |H| > 1 = \binom{n}{1} + \binom{n}{2} + … + \binom{n}{s−1} esetén dim_{V C}(H) ≥ s Bizonyítás: I. Teljes indukció

II. Lefelé zárttá tétel.

III. Lineáris algebrai bizonyítás.

Az alaptétel következményei

Definíció: sh(m; H) = max{ |H|_{U}| : U ⊆ V, |U| = m }. Megjegyzés: sh(m, H) ≤ 2^{m}. Megjegyzés: Ha sh(m, H) = 2^{m} és m′ < m, akkor sh(m′, H) = 2^{m′}. Megjegyzés: dim_{V C}(H) = max{ m : sh(m, H) = 2^{m} }. Következmény: Legyen H egy halmazrendszer a végtelen V halmaz felett. Ekkor vagy sh(m; H) = 2^{m} vagy alkalmas p(H) és M(H) függvényekre m ≥ M(H) esetén sh(m; H) ≤ m^{p(H)}. Példa: V = ^{2}, H: félterek.

A II. bizonyítás következményei Következmény: (Bondy) Legyen H egy halmazrendszer V felett. |H| ≤ |V | esetén, van olyan v ∈ V, hogy |H|_{V \{ v }} = |H|. Megjegyzés: |H| = |V | + 1 esetén nem igaz a konkluzió. Következmény: Legyen H egy halmazrendszer V felett. |H| ≤ \frac{3}{2}|V | esetén, van olyan v ∈ V, hogy |H|_{V \{ v }} ≥ |H| − 1.

Technikák a VC dimenzió kiszámítására

dim_{V C} és τ kapcsolata