Constraint Satisfaction Problem(CSP) ·Variables:x1,.,xn∈[q] .(local)Constraints:C1,....Cm each C;is defined on a subset vbl(C)of variables C:[qlvbl(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 H=(V,E): ·Vis vertex st,Ec(W）g is set of hyperedges ·degree of vertex v∈V:#of hyperedges e3v 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, A5g-1 →Hisq-colorable ek k≥logg△+loga log△+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, △sg一H6 4-clorab ek ·Uniformly and independently color each v∈V a random color∈[q] ·Bad event A,for each hyperedge∈Ec()）:ismonochromatie ·P[A。]≤p=g1-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[A1andd≌max;lTA)l epd+1)≤1→Pr[A,A>0 1 a1=…=am=dt1 Lovasz Local Lemma (asymmetric case): 3a1,,0m∈[0,1)： i,PA≤aΠ1-a)→ 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): 3a1,,am∈[0,1)： i, PrA≤aⅡ- 可- A,∈TA) chain rule ei下--rki- Induction Hypothesis (1.H.): Voistinct Pr 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 )