Lovász-féle lokális lemma
A Wikipédiából, a szabad lexikonból.
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.
[szerkesztés] A tétel állítása
Legyen G egyszerű gráf a pontokon, amiben minden pont foka legfeljebb d. Tegyük fel, hogy minden vi ponthoz hozzá van rendelve egy Ai esemény, amire és minden Ai független azon Aj eseményektől, amelyekre vj nincs összekötve vi-vel. Ekkor