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.$