Example:the r-partite Turan problem Consider an r-partite graph,at least plVilVil edges between every pair (Vi,Vi). Va V V2 Question:at what density p must G contain K,?
Question: at what density 𝜌 must G contain 𝐾𝑟? Example: the r-partite Turán problem Consider an r-partite graph, at least 𝜌 𝑉𝑖 |𝑉𝑗 | edges between every pair (𝑉𝑖 , 𝑉𝑗)
Graph G with m vertices andp=(p1,,Pm)>0,let pr=Ilie Pi Alternating-sign independence polynomial: An alternative form of the polynomial: 。=。(例=∑(-1)四p 9s=qs()= ∑(10np IEInd,IES IEInd,SEI Shearer region:S =pE(0,1)m:VS [m],qi(p)>0 ={i∈(0,1)m:I∈Ind,q(p)>0} Tight Lovasz Local Lemma (Shearer 1985): 币eS Each event sets 41,...,4m where p(Ai)=pi and the dependency graph is Gsatisfies 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 ·PrA1A=qo=am Ind: Independent set of G
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 Graph G with m vertices and 𝑝 Ԧ = 𝑝1, ⋯ , 𝑝𝑚 > 0, let 𝑝𝐼 = ∏𝑖∈𝐼 𝑝𝑖
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 qs=qs(D=∑（←1）s1p IEInd,IES IEInd,SCI Lemma 1 For each S∈[ml,as=∑YEIml\sqr ∑9w=∑∑(-1)nwp (definition) YE[ml\S Y≤m]\s IEInd,Ycl =∑p'∑(-Dnm (Y∈I\S) =∑(-1)p (power set of IS is 2\5l) IEInd:I\S as (definition)
Lemma 1 For each 𝑆 ⊆ [𝑚], 𝑞 ෬ 𝑠 = ∑𝑌⊆ 𝑚 ∖𝑆 𝑞𝑌. (definition) 𝑌⊆ 𝑚 ∖𝑆 𝑞𝑌 = 𝑌⊆ 𝑚 ∖𝑆 𝐼∈Ind,𝑌⊆𝐼 −1 𝐼∖𝑌 𝑝 𝐼 = 𝐼∈Ind 𝑝 𝐼 𝑌⊆𝐼∖𝑆 −1 |𝐼∖𝑌| (𝑌 ⊆ 𝐼 ∖ 𝑆) = 𝐼∈Ind:𝐼∖𝑆 −1 |𝐼|𝑝 𝐼 (power set of 𝐼 ∖ 𝑆 is 2 |𝐼\𝑆| ) = 𝑞෬𝑠 (definition) Alternating-sign independence polynomial: 𝑞෬𝑠 = 𝑞෬𝑠 𝑝 Ԧ = 𝐼∈Ind,𝐼⊆𝑆 −1 |𝐼| 𝑝 𝐼 An alternative form of the polynomial: 𝑞𝑆 = 𝑞𝑆 𝑝 Ԧ = 𝐼∈Ind,𝑆⊆𝐼 −1 |𝐼∖𝑆| 𝑝 𝐼 Graph G with m vertices and 𝑝 Ԧ = 𝑝1, ⋯ , 𝑝𝑚 > 0, let 𝑝𝐼 = ∏𝑖∈𝐼 𝑝𝑖
Graph G with m vertices andp=(p1,,Pm)>0,let pr=Ilie Pi Alternating-sign independence polynomial: An alternative form of the polynomial: 4s=4()= ∑(-104p qs=9s()= ∑(-1)nsp IEInd,ICS IEInd,SCI Lemma 2 For eachI∈Ind,q1=p'·9mIr+(0 =∑(-1)p (definition) JEInd,ICJ =p∑∑(-1)K1pkU=1UK) KEInd KE[m]\r+(I) =p.qmj小r+(四 (definition) Ind:Independent set of G T+(): Uier T+(i)
Lemma 2 𝑞𝐼 = (definition) 𝐽∈Ind,𝐼⊆𝐽 −1 𝐽∖𝐼 𝑝 𝐽 = 𝑝 𝐼 𝐾∈Ind 𝐾⊆[𝑚]∖Γ+(𝐼) −1 |𝐾| 𝑝 𝐾 (𝐽 = 𝐼 ∪ 𝐾) = 𝑝 𝐼 ⋅ 𝑞෬ 𝑚 ∖Γ +(𝐼) (definition) Alternating-sign independence polynomial: 𝑞෬𝑠 = 𝑞෬𝑠 𝑝 Ԧ = 𝐼∈Ind,𝐼⊆𝑆 −1 |𝐼| 𝑝 𝐼 An alternative form of the polynomial: 𝑞𝑆 = 𝑞𝑆 𝑝 Ԧ = 𝐼∈Ind,𝑆⊆𝐼 −1 |𝐼∖𝑆| 𝑝 𝐼 For each 𝐼 ∈ Ind, 𝑞𝐼 = 𝑝 𝐼 ⋅ 𝑞 ෬ 𝑚 ∖Γ +(𝐼) . Ind: Independent set of G ∪𝑖∈𝐼 Γ + Γ (𝑖) +(𝐼): Graph G with m vertices and 𝑝 Ԧ = 𝑝1, ⋯ , 𝑝𝑚 > 0, let 𝑝𝐼 = ∏𝑖∈𝐼 𝑝𝑖
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=9s()= ∑(-10np IEInd,IES IEInd,SEI Shearer region:S =pE(0,1)m:VS [m],qi(p)>0} ={∈(0,1)m:∀l∈Ind,qu(p)>0} 个 Lemma 3 q≥0H1∈Ind VSE [m] as≥0HS∈[m>q1≥pm.mV1eInd =∑ qy (Lemma 1) YEIml\S ∑ qy (qy=0ifY度Ind) YEIndAYE[m]\s ≥q0 (0∈IndA0∈[m]\S)
Lemma 3 (Lemma 1) = 𝑌∈Ind∧𝑌⊆ 𝑚 ∖𝑆 𝑞𝑌 (𝑞𝑌 = 0 if 𝑌 ∉ Ind) ≥ 𝑞∅ (∅ ∈ Ind ∧ ∅ ⊆ 𝑚 ∖ 𝑆) Alternating-sign independence polynomial: 𝑞෬𝑠 = 𝑞෬𝑠 𝑝 Ԧ = 𝐼∈Ind,𝐼⊆𝑆 −1 |𝐼| 𝑝 𝐼 An alternative form of the polynomial: 𝑞𝑆 = 𝑞𝑆 𝑝 Ԧ = 𝐼∈Ind,𝑆⊆𝐼 −1 |𝐼∖𝑆| 𝑝 𝐼 𝑞𝐼 ≥ 0 ∀ 𝐼 ∈ Ind Shearer region: 𝒮 = {𝑝 Ԧ ∈ 0,1 𝑚: ∀𝑆 ⊆ [𝑚], 𝑞෬𝐼 𝑝 > 0} = {𝑝 Ԧ ∈ 0,1 𝑚: ∀𝐼 ∈ Ind, 𝑞𝐼 𝑝 > 0} 𝑞 ෬ 𝑠 ≥ 𝑞∅ ∀ 𝑆 ∈ [m] 𝑞 ෬ 𝑠 ≥ 0 ∀ 𝑆 ∈ [m] 𝑞𝐼 ≥ 𝑝 𝑚 ⋅ 𝑞 ෬ 𝑚 ∀ 𝐼 ∈ Ind 𝑞෬𝑠 = 𝑌⊆ 𝑚 ∖𝑆 𝑞𝑌 Graph G with m vertices and 𝑝 Ԧ = 𝑝1, ⋯ , 𝑝𝑚 > 0, let 𝑝𝐼 = ∏𝑖∈𝐼 𝑝𝑖