Can the “mutual independence” condition in the Lovász local lemma be weakened?

Question

The Lovász local lemma, as stated in Corollary 5.1.2 here, is given as follows.

Lemma. Let $A_1, \ldots, A_k$ be events such that each $A_i$ has probability at most $p$ and such that each $A_i$ is mutually independent of all but at most $d$ of the $A_j$'s. Then if $ep(d+1) \leq 1$, the probability that none of the $A_i$'s occur is positive.

I have a few questions about the assumptions needed for the above lemma. Looking at the proof given in the Wikipedia article here, it appears that one does not require each $A_i$ to be mutually independent of all but at most $d$ of the $A_j$'s. Instead, all one requires is that$$\text{Prob}\left(A_i \mid \bigwedge_{j \in S} \overline{B_j} \right) = \text{Prob}(A_i),$$where $S = \{1, \ldots, k\} - \Gamma(A_i)$, where $\Gamma(A_i)$ is the dependency locus of $A_i$. I think that the above condition appears to be considerably weaker than mutual independence; indeed, mutual independence means that $$\text{Prob}\left(A_i \wedge \bigwedge_{j \in S} \overline{B_j}\right) = \text{Prob}(A_i) \cdot \prod_{j \in S} \text{Prob}(\overline{B_j}).$$

Am I right to say that mutual independence is not required?

Also, is there a reason why the constant $e$ in the statement of the Lovász local lemma is optimal? Several sources seem to agree on this. It seems somewhat arbitrary to me, and I feel like a smaller constant can be achieved by being more careful in the proof.

Thanks in advance!

Answer 1

The Lopsided Lovasz Local Lemma relaxes the mutual independence condition to negative dependence. We assume we have events $A_1, \ldots, A_n$, with a lopsidependency graph $G$ defined on $[n]$ s.t. for every event $A_i$ and every $S \subseteq [n] \setminus \Gamma^+(i)$, $$ \Pr\left(A_i \mid \bigwedge_{j \in S}{\bar{A_j}}\right) \le \Pr(A_i). $$ As you (sort of) suggest, the classical inductive proof of LLL works fine with the lopsidependency graph in place of the depdendency graph. This answers your question because the negative dependence condition is only weaker than the equality you wrote. See these notes by Vondrak for some applications.

The tightness of the constant $e$ (in the limit) was shown by Shearer, who characterized the smallest probabilities that guarantee a local lemma-type statement for any given dependency graph. There are fascinating connections with statistical mechanics, covered in a paper of Scott and Sokal.

Answer 2

The formulation on p.70 of the 4th edition of The Probabilistic Method by Alon and Spencer is along the lines you state.