The Lovasz sieve m bad event:41,42,...,Am Goal: 小 (★) union bound:Pr[A<1> (★) ● principle of inclusion exclusion(PIE): s=2-1051r 小：→ S≠0 ●LLL: every 4;is independent of all (degree≤ but≤d other bad events i:Pr[A]≤4d
The Lovász Sieve m bad event: A1, A2, …, Am Goal: • union bound: • principle of inclusion exclusion (PIE): (★) ∑ 𝑖=1 𝑚 𝑃𝑟[𝐴𝑖 ] < 1 (★) ∑ 𝑆⊆{1,…,𝑚} 𝑆≠∅ (−1) |𝑆|−1𝑃𝑟 ሥ 𝑖∈𝑆 𝐴𝑖 < 1 (★) • LLL: (★) (degree ≤ d) every Ai is independent of all but ≤ d other bad events ∀𝑖: 𝑃𝑟[𝐴𝑖 ] ≤ 1 4𝑑 𝑃𝑟 ሥ 𝑖=1 𝑚 𝐴𝑖 > 0
m bad event:A1,42,...4m Lovasz Local Lemma (asymmetric version): 3a1,Q2,…,Qm∈[0,1) Vi:Pr[A≤aiI-) 〉m m Ha-@) j~i:A;and 4j are adjacent in the dependency graph Example: A2 A1(X1,X4) A4(X4) A3 A2(X1,X2) A5(X3) A5 A4 A3(X2,X3) dependency graph X1,X2,X3,X4 (max degree d) are mutually independent
m bad event: A1, A2, …, Am 𝐴1(𝑋1, 𝑋4) 𝐴2(𝑋1, 𝑋2) 𝐴3(𝑋2, 𝑋3) 𝐴4(𝑋4) 𝐴5(𝑋3) 𝑋1, 𝑋2, 𝑋3, 𝑋4 are mutually independent dependency graph Example: (max degree d) Lovász Local Lemma (asymmetric version): 𝑃𝑟 ሥ 𝑖=1 𝑚 𝐴𝑖 > ∏ 𝑖=1 𝑚 (1 − 𝛼𝑖) ∃𝛼1, 𝛼2, … , 𝛼𝑚 ∈ [0,1) ∀𝑖: 𝑃𝑟[𝐴𝑖 ] ≤ 𝛼𝑖 ∏ 𝑗∼𝑖 (1 − 𝛼𝑗) j~i: Ai and Aj are adjacent in the dependency graph
The Lovasz Sieve m bad event:41,42,...Am Goal: () ● union bound:Pr[A<1> (★) ● principle of inclusion exclusion(PIE): ∑(-1)s-1Pr ssf1,...m} S≠0 LLL: every 4;is independent of all (degree≤d) but≤d other bad events i:Pr[Ail≤4d (女)
The Lovász Sieve m bad event: A1, A2, …, Am Goal: • union bound: • principle of inclusion exclusion (PIE): (★) ∑ 𝑖=1 𝑚 𝑃𝑟[𝐴𝑖 ] < 1 (★) ∑ 𝑆⊆{1,…,𝑚} 𝑆≠∅ (−1) |𝑆|−1𝑃𝑟 ሥ 𝑖∈𝑆 𝐴𝑖 < 1 (★) • LLL: (★) (degree ≤ d) every Ai is independent of all but ≤ d other bad events ∀𝑖: 𝑃𝑟[𝐴𝑖 ] ≤ 1 4𝑑 𝑃𝑟 ሥ 𝑖=1 𝑚 𝐴𝑖 > 0
Graph G with m vertices and节=(p1,…,pm)>0,let pr=Πte Pi Alternating-sign independence polynomial: An alternative form of the polynomial: 。=,()=∑(-1)叫川p 9s=qs()= ∑(-1)nsp IEInd,IES IEInd,SEI Shearer region:s={i∈(0,1)m:S∈[m],ai()>0} ={i∈(0,1)m:H1∈Ind,qu()>0} Tight Lovasz Local Lemma(Shearer 1985): 币ES Each event sets 41,...,4m where p(Ai)=pi and the dependency graph isGsatisfies Pr Extremal case:the dependency events are exclusive ds:the probability that none of the events in s occur. .qs:the probability that the set of occurring events is exactly s ·Pr∧1A=qo=4m Ind: Independent set of G
Graph G with m vertices and 𝑝 Ԧ = 𝑝1, ⋯ , 𝑝𝑚 > 0, let 𝑝𝐼 = ∏𝑖∈𝐼 𝑝𝑖 Alternating-sign independence polynomial: 𝑞෬𝑠 = 𝑞෬𝑠 𝑝 Ԧ = 𝐼∈Ind,𝐼⊆𝑆 −1 |𝐼| 𝑝 𝐼 An alternative form of the polynomial: 𝑞𝑆 = 𝑞𝑆 𝑝 Ԧ = 𝐼∈Ind,𝑆⊆𝐼 −1 |𝐼∖𝑆| 𝑝 𝐼 Shearer region: 𝒮 = {𝑝 Ԧ ∈ 0,1 𝑚: ∀𝑆 ⊆ [𝑚], 𝑞෬𝐼 𝑝 Ԧ > 0} = {𝑝 Ԧ ∈ 0,1 𝑚: ∀𝐼 ∈ Ind, 𝑞𝐼 𝑝 Ԧ > 0} Tight Lovász Local Lemma (Shearer 1985): Each event sets A1,…,Am where 𝑝 𝐴𝑖 = 𝑝𝑖 and the dependency graph is G satisfies Pr ٿ=��1 𝑚 𝐴𝑖 > 0 𝑝 Ԧ ∈ 𝒮 Ind: Independent set of G Extremal case: • 𝑞෬𝑠 : the probability that none of the events in S occur. • 𝑞𝑆 : the probability that the set of occurring events is exactly S • Pr ٿ=��1 𝑚 𝐴𝑖 = 𝑞∅ = 𝑞෬[𝑚] the dependency events are exclusive
Symmetric Asymmetric Cluster Shearer's LLL LLL Expansion Lemma
Shearer ’s Lemma Cluster Expansion Asymmetric LLL Symmetric LLL