Lovász-féle lokális lemma

A Wikipédiából, a szabad enciklopédiábó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.

A tétel állítása[szerkesztés | forrásszöveg szerkesztése]

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.