I have 2 question regarding Lovasz Local Lemma.
- In the book Probability and Computing: Randomized Algorithms and Probabilistic Analysis , it is shown that $Pr(\cap_{i=1}^n \overline{E_i}) \ge (1-2p)^n $ while proving Lovasz Local Lemma(Symmetric case). If $p=1/2$ ,then this expression is not strictly greater than 0, hence there is finite chance that some of the "bad" events might occur. Should this condition not be specified beforehand.
- $e(m(m-1)+1)k(1-\frac{1}{k})^m \le 1$ then $m > (3+o(1))k\log k$. How to prove this? Here $e$ is the base of natural logarithm, and m,k are positive integers.