Lovasz Local Lemma (asymmetric version): 3:A→[0,1) HA∈A:Pr[A]≤aAI(1-aB) (1-A) AEA BEr(A) VA∈凡：A=1-aA A HA CLA三1+LA 1 (1-B)= 1十HA BETCA) 1+B =LA BEr(A) BEr+(A 1+B HA HA IIBEr+(A)(1+B)EIsr+(A)IIBEI B Example: 。+(A)={A1=A,A2} ·ΠBer+A(1+B)=1·1+A1·1+1·A2+A1·A2 inclusive neighborhood: T+(A)会T(A)U{ALovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝛼𝐴 ∏ 𝐵∈Γ(𝐴) (1 − 𝛼𝐵) ∃𝛼: 𝒜 → [0,1) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 (1 − 𝛼𝐴) ∀𝐴 ∈ 𝒜: 𝜇𝐴 = 𝛼𝐴 1 − 𝛼𝐴 𝛼𝐴 = 𝜇𝐴 1 + 𝜇𝐴 𝛼𝐴 ෑ 𝐵∈Γ 𝐴 1 − 𝛼𝐵 = 𝜇𝐴 1 + 𝜇𝐴 ෑ 𝐵∈Γ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ෑ 𝐵∈Γ+ 𝐴 1 1 + 𝜇𝐵 = 𝜇𝐴 ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴} • Γ + 𝐴 = {𝐴1 = 𝐴, 𝐴2} • ∏𝐵∈Γ+ 𝐴 1 + 𝜇𝐵 = 1 ⋅ 1 + 𝜇𝐴1 ⋅ 1 + 1 ⋅ 𝜇𝐴2 + 𝜇𝐴1 ⋅ 𝜇𝐴2 Example: