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

Halmazrendszerek színezése (folytatás)

Lemma: |V | = 2r^{2} esetén τ^{∗}(H_{V,r} ≤ \frac{\sqrt{e}}{2}2^{r}. Tétel: τ(H) ≤ (1 + log Δ(H))τ^{∗}(H) Következmény: |V | = 2r^{2} estén τ(H_{V,r}) ≤ \sqrt{e}r^{2}2^{r}. Következmény: Létezik H r-uniform halmazrendszer, \sqrt{e}r^{2}2^{r} éllel, amely nem 2-színezhető.

⋆  ⋆  ⋆

Más értelemben (mint az élek száma) vett kis halmazrendszerek is garantáltan 2-színezhetőek? Tétel: Ha H minden élet legfeljebb 2^{r−3} másik él metszi, akkor χ(H) ≤ 2.

Valószínűségszámítási módszer, de nem olyan egyszerű mint a korábbi alkalmazások.