Lovasz Local Lemma (LLL) ·“Bad”events A1,,A,where all Pr[Al≤p Dependency degree d: each A;is“dependent"of≤d other events Lovasz Local Lemma [Lovasz and Erd6s 1973;Lovasz 1977]: +s1一[可0 。The“LLL”condition: Bad events are not too likely to occur individually. Bad events are not too dependent with each other.Lovász Local Lemma [Lovász and Erdős 1973; Lovász 1977]: ep(d + 1) ≤ 1 • “Bad” events A , where all 1,…, Am Pr[Aj ] ≤ p Lovász Local Lemma (LLL) ⟹ Pr [ m ⋀ i=1 Ai ] > 0 Dependency degree : each is “dependent” of other events d Ai ≤ d • The “LLL” condition: • Bad events are not too likely to occur individually. • Bad events are not too dependent with each other