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

Definíció: Él, pont elhagyása. Pont levágása. Definíció: Részhipergráf, parciális részhipergráf. Feszített részhipergráf, feszített parciális részhipergráf. Feszítő parciális részhipergráf. Definíció: Kiegyensúlyozott halmazrendszer. Páratlan gráfkör nem részhipergráfja. Példa: (Kiegyensúyozott halmazrendszerre) Totálisan unimoduláris halmazrendszerek. Definíció: Kör. Kiegyensúlyozott kör. Szép kör. Megjegyzés: Alternatív definició a kiegyensúlyozott halmazrendszerre: nincs kiegyensúlyozott páratlan köre. Megjegyzés: Kiegyensúlyozott halmazrendszer a páros gráfok egy általánosítása. Definíció: 2-színezhetőség. Definíció: Halmazrendszerek kromatikus száma. Lemma: Kiegyensúlyozott halmazrendszerek 2-színezhetők. Megjegyzés: Megfordítása nem igaz. Példa: (Kőnig-tulajdonságú halmazrendszerre) Kiegyensúlyozott halmazrendszerek.

Normális hipergráfok

Definíció: H normális, ha minden parcialis részhipergráfja Kőnig-tulajdonságú. (N) Megjegyzés: Ha H Kőnig-tulajdonságú, akkor minden parciális részhipergráfra τ^{∗}(H) = ν^{∗}(H) egész szám. (N′)

A fenti megjegyzés megfordítható. Tétel: (N′) ⇒ (N). Bizonyítás:

⋆

Definíció: Élszínezés, élkromatikus szám χ_{e}(H). Definíció: H élszinezési-tulajdonsága: Minden H′ parciális részhipergráfra Δ(H′) = χ_{e}(H′). (D) Megjegyzés: Ha H hipergráf, akkor a párhuzamos élek kihathatnak a Δ(H) és χ_{e}(H) értékekre is. Definíció: Multiplicitás módosítással nyert hipergráf. Megjegyzés: Élelhagyással nyert hipergráf egy multiplicitás módodítással nyert hipergráf. Definíció: Minden H′ multiplicitás módosítással nyert hipergráfra Δ(H′) = χ_{e}(H′). (D′) Megjegyzés: Nyilvánvalóan (D′) ⇒ (D).

A fenti tétel megfordítható. Tétel: (D) ⇒ (D′). Bizonyítás: Indukció |H′|-ra.

⋆

Tétel: (Lovász László) (N) és (D) ekvivalens. Bizonyítás: (D) ⇒ (N): Elég (D′) ⇒ (N′)-t igazolni. Ehhez elég belátni, hogy (D′) esetén ν^{∗}(H) egész. Igazoljuk, hogy \frac{ν_{k}(H)}{k} = ν(H).

⋆

A perfekt gráf tétel bizonyítása.