Lovász-féle lokális lemma

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 $v_1,\dots,v_n$ pontokon, amiben minden pont foka legfeljebb d. Tegyük fel, hogy minden $v_i$ ponthoz hozzá van rendelve egy $A_i$ esemény, amire $P(A_i)\leq\frac{1}{4d}$ és minden $A_i$ független azon $A_j$ események együttesétől, amelyekre $v_j$ nincs összekötve $v_i$-vel. Ekkor

$P(\overline{A_1}\dots\overline{A_n})>0.$