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)\le 1$.

Let $A_1,\dots ,A_m$ be bad events with a lopsidependency graph. If numbers $x_i\in [0,1)$ satisfyfor every $i$, then $\mathbb{P}({\bigcap }_i{A}_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.