Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For $\mathcal{A} = \{ A_1, \ldots, A_n \}$, a finite set of events in the probability space $\Omega$, the condition in Lovasz local lemma is existence of an assignment $x : \mathcal{A} \rightarrow (0,1)$ such that one of the following three holds: (I wonder if the following three different ways for completing the statement of the condition are actually equivalent?)

  1. One note says $$ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B: (A,B) \in E(D)} (1-x(B)) $$ Where $\{ A_1, \ldots, A_n \}$ have a dependency graph $D$, and $E(D)$ is the set of edges of $D$.
  2. Wikipedia says $$ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B \in \Gamma(A)} (1-x(B)) $$ where $\Gamma(A)$ denote a subset of $\mathcal{A}$ such that $A$ is independent from the collection of events $\mathcal{A} \setminus (\{A \} \cup \Gamma(A))$.
  3. Another note says $$ \forall A \in \mathcal{A} : \Pr[A] \leq x(A) \prod_{B \in S(A)} (1-x(B)) $$ Where $S(A): = \{B \in \mathcal{A} \setminus \{A\} | A \text{ is dependent on } B \}$.

My doubts:

  1. The first two versions seem not quite consistent with each other, since $\Gamma(A)$ can be as big as possible, such as $\Gamma(A) = \mathcal{A}$, while the dependency graph $D$ of $\mathcal{A}$ seems to capture the unique dependency relation among members of $\mathcal{A}$?
  2. I am not sure about the last version either.
  3. Which version is the correct one?
  4. Given that a dependency graph for a set of events seems not necessarily need to catpure all (in)dependency relation between events (discussed in my another post), if the Wikipedia version of the Lemma is correct, is it more general than the first version? Thanks and regards!
share|cite|improve this question
Since you're wondering about the equivalence of various conditions, it might avoid confusion if you disambiguate the ungrammatical "the following condition hold" in the first sentence. Did you mean "conditions hold" or "condition holds"? – joriki Oct 12 '12 at 14:30
@joriki: I meant there are three different ways to complete the statement for the condition of LLL. So I used "condition holds" instead of "conditions hold". Let me know if it is still not clarified. – Tim Oct 12 '12 at 14:32
Now you've introduced a different grammatical error; "the either" doesn't make any sense. I presume you mean just "either"? But there are three conditions. so it should be "any". – joriki Oct 12 '12 at 14:33
How about now? $ $ – Tim Oct 12 '12 at 14:35
There seems to be a time lag between when edits are made and when they become visible. In both cases the post appeared unchanged to me at first when you asked my opinion about the change. It still says "the either" when I reload it. – joriki Oct 12 '12 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.