events:A1,A2,...,Am each event is independent of all but at most d other events Lovasz Local Lemma(symmetric) 。Vi,PrLA≤p Pr >0 ep(d+1)≤1 i=】 Lovasz Local Lemma(general) 3a1,..,am∈[0,1) i,PrA≤aaI1-a) →m公 i三1 j心ievents: A1, A2, ... , Am each event is independent of all but at most d other events 9↵1,..., ↵m 2 [0, 1) 8i,Pr[Ai]  ↵i Y j⇠i (1 ￾ ↵j ) Pr " ^ m i=1 Ai # ￾ Y m i=1 (1 ￾ ↵i) Lovász Local Lemma (general) • ∀i, Pr[Ai] ≤ p • ep(d + 1) ≤ 1 Pr" ^ m i=1 Ai # > 0 Lovász Local Lemma (symmetric)