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

Tétel: Lovász lokális lemma.

Példa: Események függetlensége. Esemény teljes függetlensége egy esemény halmaztól. Ω: alacsony fokú polinomok egy véges test felett. Események: egy adott x pontban f érték felvétele.

Bizonyítás: (Formalizmus nélkül.) Indukcióval bizonyítunk egy erősebb állítást.

Következmény: Legyen H egy r-uniform halmazrendszer, amely minden élét legfeljebb 2^{r−3} másik metsz. Ekkor χ(H) ≤ 2.

Bizonyítás: Valszám módszer Lovász-lemmával.

Diszkrepancia

Definíció: χ : V → { −1, 1 }, χ(H), discr(H, χ), discr(H).

Példa: V: egy egyenes véges sok pontja, H: intervallumok. discr(H) = 1

Példa: V: egy n × n-es négyzetrács, H: félsíkkal levágható részhalmazok, χ: sakktábla színezés. \frac{n}{2} ≤ discr(H, χ) ≤ n.

Példa: V: egy négyzetrács véges ponthalmaza. H: a rácsegyenesekre eső ponthalmazok. discr(H) ≤ 1.

Tétel: discr(H) ≤ \sqrt{2r log 2|H|}.

Bizonyítás: Valszám módszer: R_{H} = R_{H}^{1} ˙∪R_{H}^{−1}, ahol R_{H}^{1} az az esemény, hogy χ(H) ≥ x. x választása úgy, hogy P rob(R_{H}^{1}) ≤ \frac{1}{2|H|} teljesüljön. P rob(R_{H}^{1}) becslése Chernoff-egyenlőtlenséggel.

⋆

Tétel: (Beck—Fiala) discr(H) ≤ 2Δ(calH) − 1.

Bizonyítás: χ : V → [−1, 1]. Fixált, lebegő pontok. Biztonságos, veszélyes halmazok. χ_{0} → χ_{1} → χ_{2} → χ_{3} → χ_{4} → χ_{5} → … színezések definic’lása a következő ígéretekkel: Ig_{1} Fixált elemeken nem változtatjuk a színez’est, speciálisab fixáltak maradnak. Ig_{2} Veszélyes halmazok súlya 0 és változtatás után is az marad (még ha a változtatás meg is változtatja a

kategóriáját). Ig_{3} Minden változtatás növeli a fixált elemek számát.

Ig_{1} megtartaaható, ha minden változtatás előtt a lebegő elemekre egy változót vezetünk be és ezekre írjuk fel feltételeinekt. Ig_{2} megtartható lineáris egyenletek felírásával. Ig_{1}∧Ig_{2} megtartható egy kis szabadsági fokkal is mivel az egyenletrendszernek van határozatlansága és megoldása is. A szabadsági fok használható Ig_{3} betartására. Az utolsó színezés lebegő elemeinek értékét kerekítve olyans zínez’est akpunk, amelya z állítást igazolja.

⋆  ⋆  ⋆

A félév hátralevő részéről néhány szó.