Rafał KALINOWSKI

(WMS, AGH)

Lokalny lemat Lovásza

Lokalny lemat Lovásza (LLL) jest zaawansowanym narzędziem metody probabilistycznej Erdosa. Udowodnili go w 1975 roku Pál Erdos i László Lovász i zastosowali do rozwiązania pewnego problemu dotyczącego kolorowania prostej. Ciekawy dowód tego ostatniego rezultatu wykorzystuje, oprócz LLL, m.in. twierdzenie Tichonowa dla iloczynu kartezjańskiego nieprzeliczalnej rodziny przestrzeni zwartych.

Oto LLL w wersji symetrycznej:
Niech $F$ będzie grafem, w którym zbiorem wierzchołków jest skończona rodzina zdarzeń $V(F)=\{A_1,\ldots,A_n\}$ przestrzeni probabilistycznej $(\Omega,\Sigma ,P)$, przy czym każde zdarzenie $A_i$ jest niezależne od rodziny $V(F)\setminus (N_F(A_i)\cup A_i)$ zdarzeń niesąsiednich. Jeżeli $P(A_i)\leq ( e(\Delta (F)+1))^{-1}$ dla każdego $i,$ to

$$P(\bigcap_{i=1}^n \bar {A_i})>0.$$

Podana będzie również lepsza wersja LLL (czyli LLLL) i jej zastosowanie.

Serdecznie zapraszamy wszystkich chętnych !