Lovász-féle lokális lemma

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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]

Legyen G egyszerű gráf a pontokon, amiben minden pont foka legfeljebb d. Tegyük fel, hogy minden ponthoz hozzá van rendelve egy esemény, amire és minden független azon események együttesétől, amelyekre nincs összekötve -vel. Ekkor