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: (𝐴) ≜ Γ(𝐴) ∪ {𝐴}
LLL condition:u:A→(0，+o) VS A:as PrInAEsA], VA∈A:PrA]≤nep1Er+Tine ko HA 4s ΣΠa Indep.IES AET Example: ·9A=Pr[n4eAA ·hrtA=∑inaep.Ier+ATIBEI HB ·A=儿A-1 Pr[A≤4-1 r+(A)
LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 • 𝑞 ෬ 𝒜 = Pr[⋂𝐴∈𝒜𝐴ҧ] • • • 𝜇Γ +(𝐴) = σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Example: Pr[𝐴] ≤ 𝜇{𝐴}−1 𝜇Γ+(𝐴) 𝜇𝐴 = 𝜇{𝐴} − 1
LLL condition:]:A→(0，+oo) SSA:is≌Pr[n4esA, HA∈A:Pr[A]≤ MA 4s兰 T+(A) ∑Ia Indep.ICS AEI Example: ·9.A=Pr[nAEAA] ·hrt(A=∑indep.Isr+AIIBEIB ·4A=A-1 ·Pr[A≤HA- r+(A)
LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 • 𝑞 ෬ 𝒜 = Pr[⋂𝐴∈𝒜𝐴ҧ] • • • 𝜇Γ +(𝐴) = σ𝑖𝑛𝑑𝑒𝑝. 𝐼⊆Γ+(𝐴) ∏𝐵∈𝐼 𝜇𝐵 Example: Pr[𝐴] ≤ 𝜇{𝐴}−1 𝜇Γ+(𝐴) 𝜇𝐴 = 𝜇{𝐴} − 1
LLL condition:]:A→(0，+o) VS A:asPr[nAESA], VA∈A:Pr[A]≤ A 4s T+(A) ΣΠa Indep.IES Ael Recursive bounds: S∈A,B∈S: AB)≤9s+Pr(B)ar+(B) S∈A,BtS: sUB)≥s+Pr(B)sUr+(B) is Pr[nAES\(B)A]-Pr[B ANAES\(B)A] ≥PrInAeS\个-Pr[BANAES\+(aA BASB ≥Pr[nAee-Pr]Pr[nAer+e可 S(B) =ds\(B)-Pr(B)qs\r+(B)
𝑞 ෬ 𝑆 = Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 ∧ ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ ∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 Recursive bounds: 𝑞෬𝑆∖ 𝐵 ≤ 𝑞෬𝑆 + Pr 𝐵 𝑞෬𝑆∖Γ + 𝐵 𝜇𝑆∪{𝐵} ≥ 𝜇𝑆 + Pr(𝐵) 𝜇𝑆∪Γ +(𝐵) = 𝑞 ෬ 𝑆∖ 𝐵 − Pr(𝐵)𝑞 ෬ 𝑆∖Γ +(𝐵) ≥ Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 ∧ ⋂𝐴∈𝑆∖Γ +(𝐵)𝐴ҧ ≥ Pr ⋂𝐴∈𝑆∖ 𝐵 𝐴ҧ − Pr 𝐵 Pr ⋂𝐴∈𝑆∖Γ +(𝐵)𝐴ҧ 𝐵 ∧ 𝑆 ∖ 𝐵 𝑆ҧ 𝑆 ∖ 𝐵 ∀𝑆 ⊆ 𝒜, 𝐵 ∉ 𝑆: LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜, 𝐵 ∈ 𝑆:
LLL condition::3:A→(0，+∞) S∈A:as±Pr[n4esA, HA∈A:Pr[A]≤ MA s合 T+(A) ∑Ia Indep.IcSA∈l Recursive bounds: S∈A,BeS: 4s\(B)4s+Pr(B)qs\r+(B) VS∈A,BtS: USU(B)2 us +Pr(B)usur+(B) 4ua=∑+∑Πa I∈S Indep.IsSA∈l BEIndep.IESUB AEI B∈I∈SU{B} Indep.I∈SU{B}
∀𝑆 ⊆ 𝒜: 𝑞෬𝑆 ≜ Pr[⋂𝐴∈𝑆𝐴ҧ], 𝜇𝑆 ≜ 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 Recursive bounds: 𝑞෬𝑆∖ 𝐵 ≤ 𝑞෬𝑆 + Pr 𝐵 𝑞෬𝑆∖Γ + 𝐵 𝜇𝑆∪{𝐵} ≥ 𝜇𝑆 + Pr(𝐵) 𝜇𝑆∪Γ + ∀𝑆 ⊆ 𝒜 (𝐵) , 𝐵 ∉ 𝑆: 𝜇𝑆∪{𝐵} = 𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆 ෑ 𝐴∈𝐼 𝜇𝐴 + 𝐵∈𝐼𝑛𝑑𝑒𝑝. 𝐼⊆𝑆∪𝐵 ෑ 𝐴∈𝐼 𝜇𝐴 LLL condition: ∃𝜇: 𝒜 → (0, +∞) ∀𝐴 ∈ 𝒜: Pr[𝐴] ≤ 𝜇𝐴 𝜇Γ+(𝐴) ∀𝑆 ⊆ 𝒜, 𝐵 ∈ 𝑆: 𝐵 ∈ 𝐼 ⊆ 𝑆 ∪ 𝐵 𝐼 ⊆ 𝑆 𝐼𝑛𝑑𝑒𝑝. 𝐼 ⊆ 𝑆 ∪ 𝐵