Suppose we are trying to construct a combinatorial object satisfying a large number of restrictions. We might be coloring the vertices of a hypergraph, assigning truth values to Boolean variables, or choosing a collection of objects subject to various local constraints. A natural probabilistic strategy is to make all the choices randomly and ask whether there is a positive probability that every restriction is satisfied. For each restriction, introduce a bad event describing its failure. Our goal is to prove that all the bad events can be avoided simultaneously, or equivalently that
.
The most elementary approach is the union bound. If each event has probability at most , the probability that at least one occurs is at most
. Thus
guarantees that some outcome avoids every bad event. This is already a useful existence argument, but there is something unsatisfactory about it. The number
measures the total number of restrictions, without considering how those restrictions are related. Why should adding thousands of constraints involving completely different random variables make an existing collection of constraints more difficult to satisfy?
Consider a hypergraph whose vertices are colored independently red or blue. If every edge contains vertices, the probability that a particular edge is monochromatic is
. The union bound gives a proper two-coloring when
. But suppose there are enormously many edges and each edge meets only a few others. The event that one particular edge is monochromatic depends only on the colors of vertices in that edge. Most of the other bad events involve completely different random choices. It seems reasonable that we should be able to exploit this fact. To understand the issue, imagine the extreme situation in which all the bad events are mutually independent. Then we have the exact formula
.
Every factor is positive provided its corresponding bad event is not certain. Thus, for any finite number of mutually independent events, we can avoid all of them with positive probability, no matter how large their total probability sum is. The union bound may become useless when , even though the probability of avoiding everything is still positive. We therefore want a theorem that lies somewhere between the union bound and complete independence. We do not expect to treat arbitrary dependent events as though they were independent. But if each event interacts with only a small number of others, perhaps we can show that the whole system behaves sufficiently like an independent system to guarantee a good outcome.
This is the problem addressed by the Lovász Local Lemma. The question is how one would discover its proof. The usual statement involves auxiliary numbers satisfying inequalities of the form
. At first sight, these numbers and products may seem specially designed to make an induction work. Instead of guessing them, let us begin with conditional probabilities and see why expressions of this form naturally appear.
Conditioning
Suppose we decide to avoid the bad events one after another. First we require not to occur, then
, and so on. The multiplication rule for conditional probabilities gives
This formula is worth examining carefully. It says that our chance of satisfying every restriction depends on how likely the next bad event is after we have already insisted that all the preceding bad events be avoided. It is not enough to know that every bad event is unlikely in the original probability space. We need to know that it does not become too likely after the previous restrictions have been imposed. A simple example shows the difference. Choose a number uniformly from . Let
be the event that the number is one, and
the event that it is two. Both have probability
. They cannot occur together. If we condition on
not occurring, however, the sample space has only nine possibilities, and
. Avoiding one bad event has slightly increased the probability of the other. If we also exclude the numbers three and four, the conditional probability of choosing one becomes
. If we exclude all nine other possibilities, it becomes one. Thus an event that was originally quite unlikely can become certain after enough other events have been excluded. It is exactly what conditioning does: we restrict the sample space, and the relative size of the remaining events can change. In particular, avoiding bad events is not always helpful for avoiding other bad events. Some restrictions compete with one another. On the other hand, suppose we choose two independent uniform numbers from
. Let
be the event that the first number is one, and let
be the event that the second number is two. Now
. Excluding
does not change the distribution of the first number.
The contrast suggests what we should investigate. We need to understand which restrictions can change the probability of a particular bad event, and how much that probability can increase.
Dependency Graph
Introduce a graph whose vertices correspond to the bad events. Write
for the set of neighbors of vertex
. We require that
be independent of the entire family of events indexed by its nonneighbors, taken together. This is stronger than pairwise independence. For example, if
are independent random bits, the three bits
are pairwise independent, but the third is determined by the first two. Thus pairwise independence alone does not justify treating the dependency graph as empty. We need independence from the joint information contained in the nonneighboring events. In many combinatorial applications, constructing the graph is straightforward. If the bad event
depends on a set of independent random variables
, we connect
and
whenever
. Then the variables defining
are disjoint from all the variables defining its nonneighbors, so the required independence holds.
But there is an important subtlety. Even when is independent of distant events, we cannot simply ignore them after conditioning on its neighbors. Conditioning can create correlations between variables that were previously independent. The proof must therefore use independence at the correct stage, before introducing the neighboring restrictions. Let us return to a particular event
. Suppose we have already insisted that all events indexed by some set
are avoided. Write
. We want to control
.
Divide the set into two parts. Let
consist of the nonneighbors of
, and let
consist of its neighbors. Thus
. Because
is independent of the entire collection indexed by
, we know that
. But we still have to impose the restrictions indexed by
. A direct conditional-probability calculation gives
To see this, write the left side as . The numerator is at most
, giving the inequality. This is the essential observation behind the local lemma. The original probability
appears in the numerator. The effect of all the other restrictions enters only through the denominator, the conditional probability of avoiding the neighbors of
. The number of these neighbors may be small even when
is enormous. Thus the original problem has become much more local. If we can show that the denominator is not too small, then conditioning on arbitrarily many other bad events cannot make
excessively likely.
This suggests the right kind of proof: find an upper bound on every conditional bad-event probability, use those bounds to estimate the denominator for neighboring restrictions, and check that the resulting estimate is consistent with the bound we started with. Before introducing auxiliary variables, let us try a simple numerical guess. Suppose every bad event has probability at most , and every vertex of the dependency graph has at most
neighbors. Perhaps we can prove that, after conditioning on the avoidance of any collection of other bad events, the probability of
is at most
. Why might such a statement be plausible? If an event originally has probability
, we can afford some increase caused by neighboring restrictions. We do not need the conditional probability to remain exactly
. We only need it to stay below one, uniformly over all previous restrictions. Allowing it to double gives a little room for dependence. Suppose, inductively, that every bad event has conditional probability at most
when we condition on a smaller set of avoided events. Return to the inequality from the preceding section. We need to estimate
, where
consists of at most
neighbors. By the conditional union bound, the probability that at least one of these neighboring bad events occurs, given
, is at most
. Therefore the probability of avoiding them all is at least
. Substituting into our earlier estimate gives
. To reproduce the proposed bound
, it is sufficient that
, or
.
Thus we have discovered a simple local lemma condition: if , every conditional bad-event probability can be kept below
. The argument is an induction on the number of previously excluded events. At each step, when we estimate one of the neighbors, the conditioning set is smaller than the original one, so the inductive assumption is available.Once these conditional probabilities are bounded, the multiplication rule gives
.
This already improves dramatically on the union bound. The condition involves , not
. We may have millions of bad events, provided each one is unlikely and has only a small number of neighbors. But the number two was an arbitrary guess. Why should we allow every conditional probability to double? Perhaps different events require different amounts of room. And the conditional union bound may be wasteful: when we avoid several neighboring events, the probability of success is naturally a product of successive conditional probabilities, not simply one minus their sum. Both observations point toward the full local lemma.
Let us assign a number to every bad event
. We want this number to be an upper bound on the probability of
after any collection of other bad events has been excluded. In other words, our proposed goal is
for every
not containing
. It is useful to think of
as a probability budget. We are allowing the conditional probability of
to be larger than its original probability, but not larger than
. A budget must therefore be large enough to tolerate the effects of neighboring restrictions. But there is a competing consideration: when another event
treats
as one of its neighbors, the budget
becomes a cost. A larger
means we can guarantee only a smaller probability
of avoiding it. This gives a reason not to choose the budgets unnecessarily large. Each budget helps its own event but makes its neighbors’ estimates more difficult. We need a collection of numbers that balances these competing effects.
Return to the denominator in our basic inequality. Instead of applying the union bound, order the neighbors in
as
. By the multiplication rule, the probability of avoiding them all is the product of the probabilities of avoiding them successively, each conditioned on
and the preceding neighboring events being avoided. If our proposed budgets are valid for these smaller conditioning sets, the conditional probability that
occurs is at most
. Therefore the conditional probability that it does not occur is at least
. Multiplying, we obtain
. Notice that we have not assumed the neighboring events are independent. Their avoidance probability is written as a product by the conditional multiplication rule, and each factor is estimated separately. That distinction is important. Substituting into the basic inequality gives
.
Since , the product over the full neighborhood is no larger than the product over
. We can therefore obtain the uniform bound
.
But we wanted this conditional probability to be at most . The natural requirement is consequently
We have now found the hypothesis of the Lovász Local Lemma. The formula is not an arbitrary algebraic trick. The number is the amount of conditional risk we are prepared to tolerate for event
. The product
is the probability we can guarantee remains when we impose its neighboring restrictions. Their product must be large enough to pay for the original probability of
. Equivalently, we are looking for a self-consistent collection of conditional-probability bounds. We propose the budgets, use them to estimate how much conditioning on neighbors can increase each event’s probability, and require that the resulting conditional probabilities remain within the proposed budgets. The proof works because this self-consistency can be established inductively.
Before proving the general theorem, let us see these budgets in a small probability space. Suppose we have one hundred independent experiments. In each experiment, choose a number uniformly from . For experiment
, define two bad events:
, that the chosen number is one, and
, that it is two. Each event has probability
. Within one experiment, the two events are dependent, since they cannot occur together. Events from different experiments are independent. Thus the dependency graph consists of one hundred disconnected edges, each containing two vertices. The union bound is useless: there are two hundred bad events of probability
, and their probability sum is twenty. But the desired outcome certainly exists. In each experiment, we simply need to choose a number other than one or two. The exact probability of satisfying every restriction is
. Now examine the conditional probability that motivated our budget argument. For one experiment,
, which is approximately
. Avoiding the neighboring event increases the probability from
to
. Avoiding any number of events belonging to the other ninety-nine experiments does not change this, because those experiments are independent. We therefore need a budget slightly larger than
. Try
for every event. Each vertex has exactly one neighbor, so the local lemma condition is
. At
, the right side is
, which is larger than
.
Thus the budgets are self-consistent, and the local lemma gives the lower bound for the probability of avoiding everything. This is smaller than the exact probability
, but it proves the desired existence without using the special numerical structure of these experiments. This example illustrates two points. First, the budget is generally larger than the original event probability, because conditioning on neighboring failures can increase the risk. Second, the same small amount of room is sufficient regardless of how many independent copies of the experiment we consider. We could have one hundred, a million, or a billion experiments; the condition for each local pair would remain unchanged.
The budgets become even more useful when different vertices play very different roles. Imagine a dependency graph shaped like a star, with one central vertex and one hundred leaves. Suppose the central bad event has probability at most , while every leaf event has probability at most
. The center has one hundred neighbors, but each leaf has only one. If we try to apply the symmetric local lemma using the maximum probability
and the maximum degree
, the usual condition
fails badly. The expression on the left is about
. But the center and the leaves should not have the same budget. The center has many neighbors, so its own probability needs to be small enough to survive all those restrictions. Each leaf has only one neighbor, so the situation of an individual leaf is much simpler. Try giving the center budget
and each leaf budget
. For any leaf, the local lemma condition becomes
, which holds. For the center, the condition becomes
. The right side is approximately
, so this also holds. Thus the asymmetric local lemma proves that all the bad events can be avoided, even though the symmetric maximum-degree condition fails. There is a useful lesson in the numbers. We allowed the center a relatively large conditional-probability budget of five percent, but each leaf needed a budget of only
percent. Consequently, when we considered the center, the cost of avoiding each leaf was only a factor of
. The product of one hundred such factors remained large enough to control the center. Conversely, each leaf had to pay only for avoiding the single central event, leaving a factor of
. The budgets adapt to the local structure. This is why the general form of the lemma is substantially more useful than a statement involving only the largest event probability and the largest dependency degree.
Lovász Local Lemma
We can now state the Lovász Local Lemma precisely. Let be events with dependency graph
. Suppose there are numbers
such that
for every
. Then
We have essentially discovered the proof already. What remains is to make sure that the argument is logically valid. We want to prove, simultaneously for every event and every set
not containing
, that
. We do this by induction on the size of
. If
is empty, the claim is simply
, which follows from the hypothesis because the product of neighboring factors is at most one. Now suppose the claim is known for all conditioning sets of size smaller than
. Separate
into the nonneighbors
and neighbors
of
. If
is empty, independence gives
.
Otherwise, order the vertices of as
. The probability
is a product of conditional probabilities of avoiding the neighboring events successively. At the stage when we consider
, the conditioning set consists of
and the preceding
neighbors. This set is strictly smaller than
, so the induction hypothesis tells us that the conditional probability of
is at most
. Thus
. Using the basic conditional-probability inequality,
This closes the induction. The argument also ensures that all the conditioning events involved have positive probability, since each additional restriction leaves a conditional probability of at least . Finally, order the bad events arbitrarily and use the multiplication rule from the beginning of the article. Every factor in that product is at least
, giving the required positive lower bound. The proof is short once the budgets have been found. But the important part is understanding why the budgets were introduced. They are bounds on conditional risks. The neighborhood product appears because we must pay for the restrictions that can actually influence a particular bad event. The induction works because the budgets reproduce themselves after this payment.
Symmetric version
In many applications we do not want to choose a different budget for every event. Suppose every bad event has probability at most and has at most
neighbors. If we choose the same budget
everywhere, it is sufficient that
. We need to balance two competing effects. Increasing
gives the event more room, but decreases every factor
corresponding to a neighbor. The best choice is the value of
that maximizes
. Differentiating gives
, so the maximum occurs at
. Substitution gives the sufficient condition
For large , this is approximately
. The slightly simpler and widely used condition is
. The appearance of
is therefore a consequence of optimizing the budgets. Each event must reserve roughly a fraction
of probability for its own conditional risk, while avoiding its
neighbors costs a factor approximately
. This is the origin of the familiar threshold. It is not a mysterious constant associated with dependency graphs; it comes from balancing the amount of conditional risk we allow against the cost of excluding neighboring events.
The local lemma is particularly effective when a bad event involves only a small collection of independent random choices. For example, consider a -uniform hypergraph. Color every vertex independently red or blue. For each edge
, let
be the event that
is monochromatic. As we observed earlier,
. Events corresponding to disjoint edges are independent, so we join two bad events whenever their edges intersect. If every edge intersects at most
other edges, the local lemma proves that the hypergraph is two-colorable whenever
. Suppose
and
. Then each bad event has probability
, and the condition holds. The hypergraph can have arbitrarily many edges. What matters is that a particular edge intersects relatively few others compared with how unlikely it is to be monochromatic.
A similar argument works for satisfiability. Suppose every clause of a Boolean formula contains distinct variables, and each clause shares variables with at most
others. Assign independent uniform truth values to all variables. Each clause is violated with probability
, so
guarantees that some assignment satisfies every clause.
These examples reveal why the local lemma is a natural tool for combinatorics. A bad event usually comes from one local obstruction: a monochromatic edge, an unsatisfied clause, or a forbidden local pattern. The probability of that obstruction can be very small because it requires several random choices to align in a particular way. At the same time, the obstruction interacts only with those other restrictions that share some of its random variables. If the event probability is sufficiently small compared with the size of this neighborhood, all the local obstructions can be avoided simultaneously.
There is also a limitation. The lower bound may be astronomically small if there are many events. The lemma guarantees the existence of a good outcome, but it does not by itself give an efficient procedure for finding one. In the independent-variable setting, the Moser–Tardos resampling algorithm supplies a constructive version: whenever a bad event occurs, we resample the variables on which it depends. The analysis of this algorithm again depends on controlling how local failures can influence one another.
Shearer’s Lemma
We have used the dependency graph mainly through the neighborhoods . The symmetric version remembers only the maximum degree, while the asymmetric version remembers the individual neighborhoods and their budgets. But a graph contains still more information. In particular, the neighbors of a vertex may themselves be highly connected or almost completely independent. To capture this structure more precisely, consider the independent sets of the dependency graph. For any set of vertices
, define the alternating independence polynomial
The empty independent set contributes one, individual vertices contribute negative terms, and independent pairs contribute positive products. This resembles inclusion-exclusion, but retains only the products corresponding to independent sets.
Shearer’s theorem says that if for every subset
, then every system of events with dependency graph
and probabilities at most
satisfies
.
This is the optimal universal criterion based only on the dependency graph and the event probability bounds. The polynomial behaves naturally in the extreme cases. If the graph has no edges, every subset is independent, and , recovering the exact probability for mutually independent events. If the graph is complete, the only independent sets are the empty set and the singletons, so
, recovering the union-bound threshold. For a path on three vertices, the independent sets include the pair of endpoints but not either pair containing the middle vertex. Thus
. The positive term
records the independence of the two endpoints. This is information that a maximum-degree bound does not retain.
The proof of Shearer’s theorem is closely related to the conditional-probability argument we developed. If , separating the independent sets according to whether they contain
gives the deletion identity
. The actual avoidance probabilities satisfy the corresponding inequality. Comparing the ratios of the actual probabilities with the ratios of these polynomials gives an induction analogous to the one used in the local lemma. Thus Shearer’s theorem is a refinement of the same basic idea: it replaces fixed budgets
by quantities that depend on exactly which events have already been excluded.
A star provides a useful illustration. Suppose there is one central vertex and leaves, all with the same event probability
. An independent set either contains the center, in which case it contains no leaf, or excludes the center, in which case it can contain any subset of the leaves. Therefore
. For
, this is positive even at
, because
. The symmetric local lemma would require a probability below approximately
. The large improvement comes from the fact that the leaves are mutually nonadjacent. For a long path with a common probability
, the independence polynomial satisfies the recurrence
, with
and
. Its characteristic equation is
. The transition at
determines whether these polynomials remain positive for paths of arbitrary length. By comparison, the symmetric local lemma, using maximum degree two, guarantees positivity only for
. These examples explain why the full dependency graph matters. The maximum degree is a convenient summary, but it does not distinguish a star from a graph whose neighborhoods contain many additional edges. The independence polynomial records precisely which collections of vertices can occur without internal dependency edges.
Hard Core Partition function
There is also an interesting interpretation of the independence polynomial in statistical mechanics. Imagine placing particles at vertices of a graph, with the rule that adjacent vertices cannot both be occupied. A legal particle configuration is exactly an independent set. If each occupied vertex receives a weight
, the partition function is
.
Shearer’s polynomial is obtained by substituting . The partition function is important because it organizes interactions among particles. For disjoint graphs, it factors into a product, so its logarithm becomes additive. Expanding the logarithm at small activities organizes the effects of interactions into contributions from connected clusters. This is the basis of the cluster expansion. We can already see the structure in the first few terms. The logarithm of the independence polynomial begins as
. The second-order interaction terms involve edges of the graph. Nonadjacent vertices do not contribute an additional interaction at that order, because their effects separate. The connection is especially useful when studying where the independence polynomial can vanish. Scott and Sokal showed that the zero-free regions of the hard-core partition function are closely connected with the optimal Lovász Local Lemma conditions. From this viewpoint, the local lemma is part of a broader theory of how connected interactions influence partition functions and their zeros.
Conclusion
The important idea in the Lovász Local Lemma is not merely that rare events with few dependencies can be avoided. It is how we prove this without ever controlling the full joint distribution of all the bad events. We begin with the probability of avoiding everything and express it as a product of conditional probabilities. The obstacle is that conditioning on other restrictions can increase the probability of a bad event. We therefore try to control these conditional probabilities uniformly. The dependency graph gives a way to separate the restrictions that are genuinely relevant to a particular event from those that are independent of it. We first condition on the nonneighbors, which does not change the event’s original probability. We then impose the neighboring restrictions and estimate the probability cost of doing so. This leads naturally to the probability budgets. Each budget limits how much the conditional probability of
may increase. At the same time, it determines the factor
available to other events when they need to avoid
. The local lemma condition is precisely the requirement that these budgets remain consistent with one another. Once that requirement is found, the induction is almost inevitable. To control a bad event after excluding a collection of restrictions, we use bounds for the neighboring events under smaller conditioning sets. The budgets guarantee that those bounds are strong enough to reproduce the desired estimate. Finally, multiplying the conditional probabilities shows that every restriction can be satisfied simultaneously. The symmetric local lemma replaces all this information by a single probability and a maximum degree, giving the familiar condition
. The asymmetric lemma keeps individual budgets. Shearer’s theorem goes further and replaces the fixed budgets by the alternating independence polynomial, retaining the full structure of the dependency graph. The underlying principle is that a large system of local restrictions may be satisfiable not because the restrictions are independent, but because the effect of repeatedly conditioning on their avoidance can be controlled locally and consistently. This is why the local lemma works even when there are enormously many bad events, and why its proof is fundamentally about conditional probability rather than simply counting the number of possible failures.