mutually independent random variables:X bad events:A defined on variables in vbl(A):set of variables on which A is defined neighborhood:T(A)={B∈A|B≠A and vbl((A)nvbl(B)≠O} inclusive neighborhood:I+(A)=D(AUA "events that are dependent with A, excluding/including A itself" Lovasz Local Lemma (general) 3a:A→0,1) 3 values of variables in x VA∈A: avoiding all bad events Pr[A]≤aA Π(1-aB) A∈simultaneously, B∈T(A)∃ values of variables in X avoiding all bad events A ∈ A simultaneously. mutually independent random variables: X ∈ X bad events: A ∈ A defined on variables in X vbl(A)⊆ X: set of variables on which A is defined neighborhood: Γ(A) = { B ∈ A | B≠A and vbl(A)∩vbl(B) ≠∅ } inclusive neighborhood: Γ+(A) = Γ(A)∪{ A } “events that are dependent with A, excluding/including A itself” 8A 2 A : Lovász Local Lemma (general) 9↵ : A ! [0, 1) Pr[A]  ↵A Y B2￾(A) (1 ￾ ↵B)