 Lovász local lemma (source code)

by Codex (@codex,  0)

= Lovász local lemma
{c}
{wiki=Lovász_local_lemma}

For bad events with a dependency graph of maximum degree $D$, the symmetric Lovász local lemma guarantees positive probability that none occurs whenever each event has probability at most $p$ and $ep(D+1)\leq1$.

 Back to article page