The Lovász local lemma and dependency graphs

Let the vertices of a graph index bad events. It is a dependency graph when each event is independent of the sigma-algebra generated by all its nonneighbor events other than itself. Independence from each nonneighbor separately is weaker and does not suffice. An event can be pairwise independent from two others while determined by their joint information. For example, two independent fair bits and their parity are pairwise independent random bits, but the parity is fixed once both original bits are known.

The common safe construction begins with mutually independent underlying variables. Record the variables read by each bad event, and join two events whenever their recorded variable sets intersect. Disjoint supports ensure independence from the entire collection of nonneighbor events, since that collection is measurable using variables disjoint from the event’s own support. Extra edges are harmless for validity but worsen the degree bound. Missing a genuine collective dependence can invalidate the whole theorem, even when every marginal probability was computed correctly.

Suppose each event has probability at most p and the dependency graph has maximum degree at most d. The convenient symmetric criterion is $ep(d+1)\le1$. It follows by choosing comparable x-values in the asymmetric statement and bounding the resulting product. The number d counts other events adjacent to a given event, not the size of that event’s variable support and not the total number of events. A huge instance can therefore satisfy the same local criterion as a small one.

For monochromatic edges in a k-uniform hypergraph with fair independent vertex colors, a bad event has probability $2^{1-k}$. One may join two hyperedges if they intersect. A bound on how many other edges intersect a given edge supplies d directly. A vertex-degree bound can also supply an upper bound on d, but should account for all k vertices and possible overcounting. Overcounting increases d safely; undercounting can falsely certify a coloring. No algorithmic running-time guarantee is asserted by this existence version.

The proof controls the probability of one bad event after conditioning on avoidance of many others. Nonneighbors can be removed from the difficult conditioning through the dependency property, while neighbors contribute factors bounded using the chosen x-values. This is why a list of pairwise correlations is insufficient: the argument repeatedly conditions on intersections of complements. The asymmetric formulation allows very rare events to compensate for neighbors with different probabilities, rather than forcing every event into one worst-case p.

If the symmetric criterion fails, try the asymmetric version, a tighter support graph, a different random experiment, or another proof. The local lemma is sufficient rather than necessary. It can also give a very small positive lower bound, so simple repeated sampling might still be impractical. Constructive resampling theorems provide additional conclusions in appropriate variable models, but they need their own algorithmic hypotheses and analysis. Here the goal is a valid finite existence certificate with all dependency assumptions exposed.