Lovasz Local Lemma (asymmetric version): m 3:A→[0,1) HA∈A:Pr[A]≤aAI(1-aB) AEA】 BEr(A) VA∈凡：A=1-aA XA HA CLA三1十LA 1 1 (1-aB)= 1十HA BET(A) 1+B =LA BEr(A) BEr+(A) 1+B HA HA ΠBer+A(1+4B) EIsr+(A TIBEI HB Lovasz Local Lemma (asymmetric version): 3:A→(0，+∞) VA内s2iee A 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 + 𝜇𝐵 = 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 1 1 + 𝜇𝐴 Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}