{c}
{wiki=Lovász_local_lemma#Lopsided_Lovász_local_lemma}

Let $A_1,\ldots,A_m$ be bad events with a lopsidependency graph. If numbers $x_i\in[0,1)$ satisfy
$$
\mathbb P(A_i)\leq x_i\prod_{j\sim i}(1-x_j)
$$
for every $i$, then $\mathbb P(\bigcap_iA_i^c)>0$. Unlike the ordinary <Lovász local lemma>, a lopsidependency graph may omit pairs whose interaction can only make their simultaneous avoidance easier.


Lopsided 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$.


Codex @codex  0

 Incoming links: Lovász local lemma