Constraint Satisfaction Problem (CSP) ·Variables:x1,,xn∈[q] (local)Constraints:C1,...,Cm each C;is defined on a subset vbl(C)of variables C:[g]vbl(C(True,False} Anyx [g]is a CSP solution if it satisfies all C1,...,C ·Examples: k-CNF,(hyper)graph coloring,set cover,unique games... vertex cover,independent set,matching,perfect matching
• Variables: • (local) Constraints: • each is defined on a subset of variables • Any is a CSP solution if it satisfies all • Examples: • -CNF, (hyper)graph coloring, set cover, unique games… • vertex cover, independent set, matching, perfect matching, … x1,…, xn ∈ [q] C1,…,Cm Ci 𝗏𝖻𝗅(Ci ) Ci : [q] 𝗏𝖻𝗅(Ci ) → {𝚃𝚛𝚞𝚎, 𝙵𝚊𝚕𝚜𝚎} x ∈ [q] n C1,…,Cm k Constraint Satisfaction Problem (CSP)
Hypergraph Coloring k-uniform hypergraph=(V,E): .Vis vertexsst ofhyperedges ·degree of vertex v∈V:#of hyperedges ev proper g-coloring of H: f:V->[g]such that no hyperedge is monochromatic He∈E,lfe)l>1 Theorem:For any k-uniform hypergraph H of max-degree A, k-1 △≤ →Hisq-colorable ek k≥1ogg△+logg logg△+O(1)
Theorem: For any -uniform hypergraph of max-degree , is -colorable k H Δ Δ ≤ qk−1 ek ⟹ H q Hypergraph Coloring • -uniform hypergraph : • is vertex set, is set of hyperedges • degree of vertex : # of hyperedges • proper -coloring of : • such that no hyperedge is monochromatic k H = (V, E) V E ⊆ ( V k) v ∈ V e ∋ v q H f : V → [q] ∀e ∈ E, | f(e)| > 1 k ≥ logq Δ + logq logq Δ + O(1)
Hypergraph Coloring Theorem:For any k-uniform hypergraph H of max-degree A, 4 → H is g-colorable ek ·Uniformly and independently color each v∈V a random color∈[qd Bad eventforeac hyperedge:eis monhromatic ·Pr[A]≤p=gl-k ·Dependency degree for bad events d≤k(△-l) ep(d+1)≤1 Apply LLL
Theorem: For any -uniform hypergraph of max-degree , is -colorable k H Δ Δ ≤ qk−1 ek ⟹ H q Hypergraph Coloring • Uniformly and independently color each a random color • Bad event for each hyperedge : is monochromatic • • Dependency degree for bad events • v ∈ V ∈ [q] Ae e ∈ E ⊆ ( V k) e Pr[Ae] ≤ p = q1−k d ≤ k(Δ − 1) Δ ≤ qk−1 ek ⟹ ep(d + 1) ≤ 1 Apply LLL
Lovasz Local Lemma (LLL) A1,...A has a dependency graph given by neighborhoods I() Lovasz Local Lemma(symmetric case): p≌max;Pr[A】andd≌max;lT(A)川 ep(d+1)≤1→Pr[Λ1A>0 1 C1=…=Cm= d+1 Lovasz Local Lemma (asymmetric case): 3a1,,am∈[0,1)： ws几-一iu i,1 1 A,∈TA)
Lovász Local Lemma (symmetric case): p ≜ max and i Pr[Ai ] d ≜ maxi |Γ(Ai )| ep(d + 1) ≤ 1 ⟹ Pr[⋀m i=1Ai] > 0 Lovász Local Lemma (LLL) • A has a dependency graph given by neighborhoods 1, …, Am Γ( ⋅ ) α1 = ⋯ = αm = 1 d + 1 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 )
A1,...,A has a dependency graph given by neighborhoods I() Lovasz Local Lemma (asymmetric case): An-=[公ia-心 3a1,,am∈[0,1)： A∈T(A) chain rule [np-li Induction Hypothesis(I.H.): iinc,4,Ag4Pr[A,1不…A≤& Basis:when k=0,trivial
• 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.): Pr [Ai ∣ Aj1 ⋯Ajk] ≤ αi chain rule ≥ m ∏ i=1 (1 − αi ) Basis: when k = 0, trivial ∀ distinct A : i , Aj1 , Aj2 , …, Ajk 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 )