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

P(\overline{A_1}\dots\overline{A_n})>0.
Más nyelveken