LLL 3a1,,am∈[0,1)s.t cond.: i,Pr[A1≤a Π (1- A∈T(A LH:PrA,|A可≤g holds for all smaller SayA,A∈IrA,Ai,A(A)l≥1 or else trivial) 1不离-不I天可 ≤a1 neighbors .non-neighbors Pr瓦Ai瓦4A ≤Pr[AI不=PrA≤%ⅡI-) (LLL cond.) A,∈TA;) ☐=·r再，1…=-mA.1… aw-)产1-
LLL cond.: ∃α s.t. 1,…, αm ∈ [0,1) ∀i, Pr[Ai ] ≤ αi ∏ Aj ∈Γ(Ai ) (1 − αj ) I.H.: Say A , j1 ,…, Ajl ∈ Γ(Ai ) Ajl+1 , …, Ajk ∉ Γ(Ai ) = Pr [AiAj1 ⋯Ajl ∣ Ajl+1 ⋯Ajk] Pr [Aj1 ⋯Ajl ∣ Ajl+1 ⋯Ajk] ≤ Pr [Ai ∣ Ajl+1 ⋯Ajk]= Pr[Ai] ≤ αi ∏ Aj ∈Γ(Ai ) (1 − αj ) (LLL cond.) Pr [Ai ∣ Aj1 ⋯Ajk] ≤ αi Pr [Ai ∣ Aj1 ⋯Ajl Ajl+1 ⋯Ajk] = l ∏ r=1 Pr [Ajr ∣ Ajr+1 ⋯Ajk] holds for all smaller k = l ∏ r=1 (1 − Pr [Ajr ∣ Ajr+1 ⋯Ajk]) ≥ l ∏ r=1 (1 − αjr) ≥ ∏ Aj ∈Γ(Ai ) (1 − αj (I.H.) ) ≤ αi (l ≥ 1 or else trivial) neighbors non-neighbors
A1,...,Am has a dependency graph given by neighborhoods I() Lovasz Local Lemma (asymmetric case): 3a41,,am∈[0,1)： i,PrA1≤a,ΠI-a) l区i A,∈TA) chain rule ei下--rki-w Induction Hypothesis (1.H.): in,4Ae…4PrA,1不…4≤g
• A has a dependency graph given by neighborhoods 1, …, Am Γ( ⋅ ) Pr [ m ⋀ i=1 Ai ] = m ∏ i=1 Pr Ai ⋀ j<i Aj = m ∏ i=1 1 − Pr Ai ⋀ j<i Aj Induction Hypothesis (I.H.): chain rule ≥ m ∏ i=1 (1 − αi ) Lovász Local Lemma (asymmetric case): ⟹ Pr [ m ⋀ i=1 Ai ] ≥ m ∏ i=1 (1 − αi ) ∃α : 1, …, αm ∈ [0,1) ∀i, Pr[Ai ] ≤ αi ∏ Aj ∈Γ(Ai ) (1 − αj ) Pr [Ai ∣ Aj1 ⋯Ajk] ≤ αi ∀ distinct A : i , Aj1 , Aj2 , …, Ajk
Lovasz Local Lemma (LLL) A1,...,A has a dependency graph given by neighborhoods I() Lovasz Local Lemma(asymmetric case): 3a1,,am∈[0,1)： Vi, A∈TA) a=…=am=dt1 1 a1=…=am=2d symmetric case: p≌max;Pr[A] d≌max;lr(i)川 }
Lovász Local Lemma (LLL) • A has a dependency graph given by neighborhoods 1, …, Am Γ( ⋅ ) p ≜ max i Pr[Ai ] d ≜ maxi |Γ(i)| symmetric case: ⟹ Pr [ m ⋀ i=1 Ai ] > 0 } Lovász Local Lemma (asymmetric case): ⟹ Pr [ m ⋀ i=1 Ai ] > 0 ∃α : 1,…, αm ∈ [0,1) ∀i, Pr[Ai ] ≤ αi ∏ Aj ∈Γ(Ai ) (1 − αj ) or ep(d + 1) ≤ 1 4pd ≤ 1 α1 = ⋯ = αm = 1 d + 1 α1 = ⋯ = αm = 1 2d
Lovasz Local Lemma (LLL) A1,...,A has a dependency graph given by neighborhoods I(.) 0.25 case): 0.20 0.15 ed+)→ 0.10 4d 0.05 10 symmetric case: p≌max;Pr[A] ep(d+1)≤1 d≌max;lT(i)l }区
Lovász Local Lemma (LLL) • A has a dependency graph given by neighborhoods 1, …, Am Γ( ⋅ ) p ≜ max i Pr[Ai ] d ≜ maxi |Γ(i)| symmetric case: ⟹ Pr [ m ⋀ i=1 Ai ] > 0 } Lovász Local Lemma (asymmetric case): ⟹ Pr [ m ⋀ i=1 Ai ] > 0 ∃α : 1,…, αm ∈ [0,1) ∀i, Pr[Ai ] ≤ αi ∏ Aj ∈Γ(Ai ) (1 − αj ) or ep(d + 1) ≤ 1 4pd ≤ 1