m bad event:AA1,A2,...Am} Lovasz Local Lemma (asymmetric version): 3u:A→(0，+o) m aet.rW≤Er oP neighborhood:T(A)B EA I A and B are adjacent in the dependency graph} inclusive neighborhood:r+(A)r(A)U{A} Cluster Expansion Lovasz Local Lemma (Bissacot et.al.2009): 3:A→(0，+∞) VA∈A:Pr[A≤Indep.I+le A →公 m bad event: 𝒜 ≜ {𝐴1, 𝐴2, … , 𝐴𝑚} Lovász Local Lemma (asymmetric version): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝐴∈𝒜 1 1 + 𝜇𝐴 Pr ሥ 𝑖=1 𝑚 𝐴𝑖 > ෑ 𝐴∈𝒜 1 1 + 𝜇𝐴 Cluster Expansion Lovász Local Lemma (Bissacot et. al. 2009): ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝐼𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∃𝜇: 𝒜 → (0, +∞) neighborhood: Γ(𝐴) ≜ {𝐵 ∈ 𝒜 ∣ 𝐴 and 𝐵 are adjacent in the dependency graph} Γ + inclusive neighborhood: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}