Is mutual independence not commutative? Necessity of directed edges in dependency digraph. Is there a point in saying something is mutually independent of something instead of saying these two things are mutually independent?
Because that is the language used in the Lovasz Local Lemma: $A_i$ is mutually independent of all the events $\{A_j\ :\ (i,j)\notin E\}$
I'm reading about the Lovasz Local Lemma and I don't understand why the graph needs to have directed edges. If there is an edge $(i,j)$ it means $i$ is dependent on $j$. Wouldn't that imply there should also be an edge $(j,i)$?
Maybe a simple example that shows the necessity of directed edges could help.
In my understanding mutual independence doesn't care about the order, but it is a binary function on sets of events.
$f:A\times A\mapsto\{0,1\}$ where $A$ is a subset of the power set of all elementary events. But the dependency graph's vertices are individual events so if we wanted to have a simple graph completely describing all the dependencies and independencies, we would need one vertex per set of events, which would be a lot of vertices (if $A_1,\dots,A_n$ are our elementary events from the lemma, then we would need $2^n$ vertices instead of just $n$ as it is the case in the Lemma), so using directed edges each elementary event has its own set of dependent events.
I guess it comes down to how much information is in a digraph versus a simple graph. There are $2^{n\choose 2}$ possible simple graphs in $n$ nodes, and that quantity squared = $2^{n(n-1)}$ directed graphs.
 A: Your understanding is right: mutual independence is, as you say, "commutative". The point here, rather, is that a "dependence digraph" (as defined in the note you linked in the comments) need not capture the exact dependence structure between the given events. Sure, it must contain every edge (undirected, or directed both ways) corresponding to dependent events; but we can also "forget" about the independence of some pairs of events, i.e. add further (directed) edges. As you might expect, throwing away information like this never yields a better bound when applying the Lovász Local Lemma: if some $x_1,\dots,x_n$ satisfies the condition of the lemma for such a directed dependency graph, then it also satisfies the condition for the undirected version, where we delete all the "extra" directed edges.
What's the point of this? In the note it is stated that in some applications, the digraph structure (i.e. throwing away information) arises naturally. But they don't give an example of this, and I don't know any, either – it would be nice if someone shared one.
