Lovász-féle lokális lemma

Ez a szócikk nem tünteti fel a független forrásokat, amelyeket felhasználtak a készítése során. Emiatt nem tudjuk közvetlenül ellenőrizni, hogy a szócikkben szereplő állítások helytállóak-e. Segíts megbízható forrásokat találni az állításokhoz! Lásd még: A Wikipédia nem az első közlés helye.

A Lovász-féle lokális lemma a kombinatorika egyik, elsősorban véletlen struktúrák vizsgálatánál használt tétele.

A tétel állítása

Legyen G egyszerű gráf a ${\displaystyle v_{1},\dots ,v_{n}}$ pontokon, amiben minden pont foka legfeljebb d. Tegyük fel, hogy minden ${\displaystyle v_{i}}$ ponthoz hozzá van rendelve egy ${\displaystyle A_{i}}$ esemény, amire ${\displaystyle P(A_{i})\leq {\frac {1}{4d}}}$ és minden ${\displaystyle A_{i}}$ független azon ${\displaystyle A_{j}}$ események együttesétől, amelyekre ${\displaystyle v_{j}}$ nincs összekötve ${\displaystyle v_{i}}$-vel. Ekkor

${\displaystyle P({\overline {A_{1}}}\dots {\overline {A_{n}}})>0.}$