The Lovász Local Lemma

You are building something — a seating plan, a wire-coloring, a schedule — and there are bad outcomes you must avoid. Maybe two rivals end up at the same table, or two signals on adjacent wires clash, or two lectures overlap. Each bad event on its own is unlikely. The trouble is there are many of them.

Can you avoid all the bad events at once? The naive answer is pessimistic: if there are $n$ bad events each with probability $p$, a union bound says bad things happen with probability at most $np$, which can exceed 1 and tell you nothing.

The Lovász Local Lemma (LLL), proved by László Lovász and Paul Erdős in 1975, gives a far sharper answer. Provided each bad event has probability at most $p$ and each event shares variables with at most $d$ others, the lemma guarantees a safe outcome exists whenever

$$ep(d+1) \le 1$$

where $e \approx 2.718$ is Euler's number. The key insight: as long as the dependency graph is sparse enough, bad events cannot gang up on you.

Below is a sparse formula: a set of Boolean variables and clauses. Each clause is a bad event — it is violated when all its literals are false. Each variable appears in only a few clauses, so the dependency graph is thin.

<!-- {{c_html_comment}} -->
<p class="hint">{{hint_para}}</p>
<div id="formula-area">
  <div id="vars-row" class="vars-row"></div>
  <div id="clauses-area" class="clauses-area"></div>
</div>
<div class="lll-badge" id="lll-badge">{{lll_label}}</div>
<div class="status" id="status">{{status_init}}</div>
<div class="btns">
  <button id="btn-rand" type="button">{{btn_rand}}</button>
  <button id="btn-fix" type="button">{{btn_fix}}</button>
  <button id="btn-reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

/* {{c_css_comment}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .7rem; line-height: 1.5; }
.vars-row { display: flex; flex-wrap: wrap; gap: 5px; margin-bottom: .7rem; }
.var-chip { display: flex; flex-direction: column; align-items: center; gap: 1px;
            cursor: pointer; padding: 3px 8px; border-radius: 7px; min-width: 38px;
            border: 1px solid #adb1b8; background: #e4e8ed;
            font-family: ui-monospace, monospace; user-select: none; transition: background .15s; }
.var-chip .vname { font-size: .72rem; color: #666; }
.var-chip .vval  { font-size: 1rem; font-weight: 700; }
.var-chip.vtrue  { background: #d4edda; border-color: #6ab187; color: #0a5c2b; }
.var-chip.vfalse { background: #fde8e8; border-color: #e08080; color: #8b1a1a; }
.clauses-area { display: flex; flex-direction: column; gap: 4px; margin-bottom: .6rem; }
.clause { display: flex; align-items: center; gap: 4px; padding: 4px 9px;
          border-radius: 8px; border: 1px solid #cdd9e3; background: #f0f4f8;
          font-family: ui-monospace, monospace; font-size: .9rem; transition: background .2s; }
.clause.sat   { background: #d4edda; border-color: #6ab187; }
.clause.unsat { background: #fde8e8; border-color: #e08080; }
.lit     { padding: 0 3px; }
.lit.neg { color: #8b1a1a; }
.sep     { color: #888; font-size: .78rem; }
.badge   { margin-left: auto; font-size: .75rem; border-radius: 10px; padding: 1px 7px;
           font-family: system-ui, sans-serif; font-weight: 600; }
.clause.sat   .badge { background: #0a7d33; color: #fff; }
.clause.unsat .badge { background: #c92f3c; color: #fff; }
.lll-badge { font-size: .8rem; color: #1d3557; background: #dce8f5; border: 1px solid #90b4d4;
             border-radius: 8px; padding: 3px 10px; margin-bottom: .5rem; display: inline-block; }
.status { font-size: 1rem; font-weight: 600; margin: .3rem 0; min-height: 1.4em; }
.status.ok   { color: #0a7d33; }
.status.bad  { color: #c92f3c; }
.status.info { color: #1d3557; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .4rem .85rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Click Randomize to assign variables at random and see which clauses are violated. Then click Fix (Moser-Tardos) to watch the algorithm resample variables one bad clause at a time until every clause is satisfied. The LLL guarantees this process terminates quickly — because sparsity prevents bad events from cascading.

The original LLL is a non-constructive existence proof. It tells you a satisfying assignment must exist, but gives no recipe for finding it. For 35 years this was an open problem.

• The symmetric LLL (Erdős–Lovász, 1975): if every bad event has probability $p \le \frac{1}{e(d+1)}$ and depends on at most $d$ others, a good outcome exists.
• The general LLL (Lovász, 1977): a weighted condition $\Pr[A_i] \le x_i \prod_{j \in \Gamma(i)}(1-x_j)$ for some $x_i \in (0,1)$ suffices, covering asymmetric cases.
• Algorithmic LLL (Moser–Tardos, 2010): Robin Moser and Gábor Tardos gave a strikingly simple randomized algorithm — repeatedly fix a violated clause by resampling its variables — and proved it terminates in polynomial expected time. The analysis relies on an entropy argument about "witness trees."
• Parallel and deterministic versions followed, and the LLL was shown to be complete for a complexity class called $\mathsf{LLL}$ (a subclass of $\mathsf{TFNP}$), placing it firmly in the landscape of total search problems related to P vs NP.

The gap between "it exists" and "we can find it" shrank to zero, but only after three decades and a beautiful algorithmic idea.

Whenever you need to satisfy many sparse local constraints at once, the LLL is the right tool:

• Graph coloring: color the vertices of a graph with $k$ colors so no two adjacent vertices share a color. Each edge is a bad event (same color on both ends). The LLL gives sufficient conditions in terms of the maximum degree.
• $k$-SAT and constraint satisfaction: a $k$-SAT formula where each variable appears in at most $\frac{2^k}{ek}$ clauses has a satisfying assignment — a direct application of the symmetric LLL.
• Packet routing: schedule messages in a network so no two packets collide on the same wire at the same time step. Each collision is a bad event; sparsity of the routing paths makes the LLL applicable.
• Combinatorial designs and coding theory: construct binary strings avoiding all forbidden patterns; the LLL provides the existence of codes with certain distance properties.
• Ramsey theory: avoid monochromatic cliques in edge-colored graphs when the graph is sparse enough.

The common thread: local sparsity turns a globally impossible-looking task into a guaranteed success.

The Lovász Local Lemma is one of the most elegant results in probabilistic combinatorics. The message is surprisingly optimistic: if bad events are rare enough and interact sparsely, you can dodge all of them at once — not just probably, but certainly.

For decades the lemma lived in the realm of pure existence. The Moser–Tardos algorithm of 2010 brought it to earth: a simple, efficient procedure that finds the good outcome the lemma promises. The analysis of that algorithm, in turn, opened new windows on entropy, randomness, and the structure of search problems.

The next time a problem asks you to satisfy a long list of local constraints, ask whether the LLL condition holds. If it does, the solution already exists — and with the right algorithm, you can find it too. See also graph coloring and SAT for closely related hardness results that show what happens when sparsity fails.