Carrying a somehow mysterious name, the Lovász Local Lemma is an intriguingly neat technique to give existence proofs. In particular, it is one of the commonly used hammers in the probabilistic method. First, let us recall what the probability method (notoriously advocated by the famous Paul Erdős) is about:
In order to show existence of a mathematical object with certain properties, one can do the following:
- Define a probability space of objects and a way of sampling it
- Show that the probability of the sought object being sampled is non-zero
Written down, this sounds almost blatantly obvious. However, with a speck of creativity, the probabilistic method can provide short and concise non-constructive existence proofs in cases where everything else fails. The non-constructive is important here – it allows us to detach ourselves entirely from the burden of actually constructing (possibly very complex) objects whose existence we are after. We will know that the sought object exists, but have no idea how to find it. Let us examine the method in an example (due to Erdős):
Example 1: Let be a complete graph on vertices and a given integer. If , then there exists a coloring of the edges of with two colors, such that every complete subgraph on vertices contains both colors.
Proof: Suppose that every edge in the graph is colored randomly with probability of picking either color. Let be the random variable counting the number of complete -subgraphs which only contain one color. We also define an indicator variable :
Then, taking expectation, we have:
By assumption, this is smaller than and we thus have . But this means that , being an integer, must be equal to for some colourings (otherwise we would have ).
In the above, we have used reasoning about expectation to show that the probability . The Lovász local lemma provides a more direct way. We combine the three most common versions of the lemma into one statement:
Let be a sequence of (bad) events, each of which happens with probability at most , and where each event is dependent on at most of them. If either of these conditions holds:
then the probability that none of the event occurs is positive.
Let’s see how the lemma can be applied in an example with the -SAT problem. Recall that the »-SAT problem« problem is, given a set of boolean variables , to decide whether a formula in »CNF«, where each clause contains precisely -literals, is satisfiable (that is, there exists an assignment of truth values to the variables, such that the formula evaluates to truth). An example of a formula may be:
Example 2: Suppose that each variable in a -SAT formula appears in at most clauses. Then it is satisfiable.
Proof: Suppose that every variable is assigned a truth value randomly, with probability for either option. Let denote the event that the -th clause evaluates to false. In such a case, all variables in the cause must be “wrong”: . As each variable in the clause is present in at most other clauses, the event is dependent on at most other events. By the Lovász local lemma, since holds, we deduce:
Lets take a look at one other example related to hypergraphs. A hypergraph is a tuple of vertices and hyperedges . Each hyperedge is a subset of the vertices. A 2-colouring of a hypergraph is an assignment of colors to vertices such that no hyperedge is monochromatic (connects vertices all of the same color).
Example 3: Let be a hypergraph where each hyperedge contains at least vertices. Find sufficient conditions for to be 2-colourable.
Solution: Assume that each vertex is colored uniformly at random with the colors. Let be the event that the hyperedge ends up monochromatic. By assumption on the number of vertices in a hyperedge, we deduce the bound on probability:
Now suppose that every hyperedge intersects any other hyperedge in at most vertices. By the Lovász Local Lemma, will be -colourable if , that is:
Thus a sufficient condition is that every hyperedge intersects any other hyperedge in at most vertices.