m bad event:A{A1,A2,...,Am} Lovasz Local Lemma (asymmetric version): 3a:A→[0,1) A∈A:Pr[A≤aAnI(1-aa） →公 II(1-@a) A∈A BEr(A) neighborhood:r(A)[BEA I A and B are adjacent in the dependency graph} Example: A2 A1(X1,X4) A A4(X4) A3 A2(X1,X2) A5 A5(X3) A4 A3(X2,X3) dependency graph X1,X2,X3,X4 (max degree d) are mutually independent m bad event: 𝒜 ≜ {𝐴1, 𝐴2, … , 𝐴𝑚} 𝐴1(𝑋1, 𝑋4) 𝐴2(𝑋1, 𝑋2) 𝐴3(𝑋2, 𝑋3) 𝐴4(𝑋4) 𝐴5(𝑋3) 𝑋1, 𝑋2, 𝑋3, 𝑋4 are mutually independent dependency graph Example: (max degree d) Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) neighborhood: Γ(𝐴) ≜ {𝐵 ∈ 𝒜 ∣ 𝐴 and 𝐵 are adjacent in the dependency graph}