# Simple Example of Dependency Digraph that is Not a Dependency Graph

In the language of the Lovász Local Lemma, a dependency graph $G$ is one in which

• each $i$ vertex corresponds to an event $A_i$ and
• each event $A_i$ is mutually independent of the collection $\{A_j \mid ij \notin E(G), i \neq j\}$.

In words, each event is mutually independent of the collection of its non-neighbors in the dependency graph.

A dependency digraph is defined similarly, except the edges are directed.

Is there a simple example of events that define a dependency digraph that is not a dependency graph?

An example of such a thing would be events $A_1$, $A_2$, and $A_3$ for which $A_1$ is mutually independent of $\{A_2, A_3\}$, but $A_2$ is not mutually independent of $\{A_1, A_3\}$.

-
As far as I know, a "dependency graph" is a directed graph itself. See mpi-inf.mpg.de/departments/d1/teaching/ss11/ProbMethod/files/…. Could you provide references for your definitions? – Tim Oct 12 '12 at 13:54
Also see my related posts math.stackexchange.com/questions/211663/…, and math.stackexchange.com/questions/211400/… – Tim Oct 12 '12 at 13:56
@Tim For me, a dependency graph has undirected edges and a dependency digraph has directed ones. I picked up this terminology from arxiv.org/abs/0905.3983. – Austin Mohr Oct 12 '12 at 19:38

Here is a simple example of events $A_1, A_2, A_3$ for which $A_1$ is mutually independent of $A_2$ and $A_3$, but $A_2$ is not mutually independent of $A_1$ and $A_3$:
Consider the probability space of words {001,010,011,101,110,111} where $A_i$ is the event that the $i$'th bit is 1. Then $Pr[A_1] = Pr[A_1|A_2] = Pr[A_1|A_3] = Pr[A_1|A_2 \wedge A_3] = 1/2$, but $Pr[A_2] = 2/3$ while $Pr[A_2|A_3] = 1/2$.