Introduction

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 nn bad events each with probability pp, a union bound says bad things happen with probability at most npnp, 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 pp and each event shares variables with at most dd others, the lemma guarantees a safe outcome exists whenever

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

where e≈2.718e \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.

Try It: Satisfy a Sparse Formula

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.

<!-- Lovász Local Lemma demo — sparse 3-SAT formula with LLL condition verified -->
<p class="hint">Each row is a clause — a <b>bad event</b> violated when all its literals are false. Clauses <b>C0/C1</b> share variable <i>c</i>; clauses <b>C2/C3</b> share <i>h</i> — the only dependencies. Click a chip to flip a variable manually.</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 condition: e · p · (d+1) = 2.718 · 0.125 · 2 ≈ 0.68 ≤ 1 ✓</div>
<div class="status" id="status">Assign variables, then check the clauses.</div>
<div class="btns">
  <button id="btn-rand" type="button">Randomize</button>
  <button id="btn-fix" type="button">Fix (Moser-Tardos)</button>
  <button id="btn-reset" type="button" class="ghost">Reset to false</button>
</div>

/* Styles for the LLL demo: variable chips and clause rows */
* { 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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Lovász Local Lemma demo: 4 clauses, 10 variables, 2 independent pairs.
// Each 3-literal clause is violated with probability p = 0.5^3 = 0.125.
// Max dependency d = 1 (clauses in the same pair share one variable).
// LLL condition: e * 0.125 * (1+1) = 0.68 <= 1 — a satisfying assignment is guaranteed.

// Variable names shown to the user as clickable chips
const VAR_NAMES = ['a','b','c','d','e','f','g','h','i','j'];

// Each clause is a list of [varIndex, polarity] literals.
// A clause [vi, pol] is satisfied when assignment[vi] === pol (true/false).
// Pair 1: C0 and C1 share variable c (index 2). Pair 2: C2 and C3 share h (index 7).
const CLAUSES = [
  [[0,true],[1,false],[2,true]],   // a v ~b v c
  [[2,false],[3,true],[4,false]],  // ~c v d v ~e
  [[5,true],[6,false],[7,true]],   // f v ~g v h
  [[7,false],[8,true],[9,false]],  // ~h v i v ~j
];

// Dependency graph: C0-C1 are neighbors; C2-C3 are neighbors; no other edges.
// LLL value e * p * (d+1) = 2.718 * 0.125 * 2 = 0.68 < 1 -- condition holds.

// Current assignment — start with a random assignment
let assignment = VAR_NAMES.map(() => Math.random() < 0.5);

function clauseSat(clause, asgn) {
  // A clause is satisfied iff at least one literal matches the assignment
  return clause.some(([vi, pol]) => asgn[vi] === pol);
}

function allSat(asgn) {
  return CLAUSES.every(cl => clauseSat(cl, asgn));
}

function renderVars() {
  const row = document.getElementById('vars-row');
  row.innerHTML = '';
  assignment.forEach((val, i) => {
    const chip = document.createElement('div');
    chip.className = 'var-chip ' + (val ? 'vtrue' : 'vfalse');
    chip.innerHTML = '<span class="vname">' + VAR_NAMES[i] + '</span>' +
                     '<span class="vval">' + (val ? 'T' : 'F') + '</span>';
    chip.addEventListener('click', () => {
      assignment[i] = !assignment[i];
      renderAll();
      setStatus('Manual flip — check the clauses.', 'info');
    });
    row.appendChild(chip);
  });
}

function renderClauses() {
  const area = document.getElementById('clauses-area');
  area.innerHTML = '';
  CLAUSES.forEach((clause) => {
    const sat = clauseSat(clause, assignment);
    const div = document.createElement('div');
    div.className = 'clause ' + (sat ? 'sat' : 'unsat');
    clause.forEach(([vi, pol], idx) => {
      const span = document.createElement('span');
      span.className = 'lit' + (pol ? '' : ' neg');
      span.textContent = (pol ? '' : '¬') + VAR_NAMES[vi];
      div.appendChild(span);
      if (idx < clause.length - 1) {
        const sep = document.createElement('span');
        sep.className = 'sep';
        sep.textContent = ' ∨ '; // OR symbol
        div.appendChild(sep);
      }
    });
    const badge = document.createElement('span');
    badge.className = 'badge';
    badge.textContent = sat ? '✓ sat' : '✗ unsat';
    div.appendChild(badge);
    area.appendChild(div);
  });
}

function renderAll() { renderVars(); renderClauses(); }

function setStatus(t, cls) {
  const s = document.getElementById('status');
  s.textContent = t; s.className = 'status ' + cls;
}

function randomize() {
  // Assign each variable independently and uniformly at random
  assignment = VAR_NAMES.map(() => Math.random() < 0.5);
  renderAll();
  setStatus(allSat(assignment) ? 'Lucky! Random assignment already satisfies all clauses.' : 'Some clauses violated — click Fix to run Moser-Tardos.',
            allSat(assignment) ? 'ok' : 'bad');
}

function moserTardos() {
  // Moser-Tardos: pick any violated clause at random and resample all its variables.
  // The LLL condition guarantees this terminates in expected polynomial time.
  let asgn = assignment.slice();
  let steps = 0;
  const MAX_STEPS = 500;
  while (!allSat(asgn) && steps < MAX_STEPS) {
    // Find all violated clauses and pick one at random
    const violated = CLAUSES.filter(cl => !clauseSat(cl, asgn));
    const cl = violated[Math.floor(Math.random() * violated.length)];
    // Resample every variable in the chosen violated clause
    cl.forEach(([vi]) => { asgn[vi] = Math.random() < 0.5; });
    steps++;
  }
  assignment = asgn;
  renderAll();
  if (allSat(assignment)) {
    setStatus(fmt('All clauses satisfied after %steps% resampling steps.', { steps: steps }), 'ok');
  } else {
    setStatus('Did not converge (very unlikely given LLL condition).', 'bad');
  }
}

document.getElementById('btn-rand').addEventListener('click', randomize);
document.getElementById('btn-fix').addEventListener('click', moserTardos);
document.getElementById('btn-reset').addEventListener('click', () => {
  assignment = VAR_NAMES.map(() => false);
  renderAll();
  setStatus('All variables set to false.', 'info');
});

renderAll();
setStatus('Assign variables, then check the clauses.', 'info');
Result
Console

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 Real Complexity

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≤1e(d+1)p \le \frac{1}{e(d+1)} and depends on at most dd others, a good outcome exists.
  • The general LLL (Lovász, 1977): a weighted condition Pr⁡[Ai]≤xi∏j∈Γ(i)(1−xj)\Pr[A_i] \le x_i \prod_{j \in \Gamma(i)}(1-x_j) for some xi∈(0,1)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 LLL\mathsf{LLL} (a subclass of TFNP\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.

Where It Matters

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 kk 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.
  • kk-SAT and constraint satisfaction: a kk-SAT formula where each variable appears in at most 2kek\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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/lovasz-local-lemma/Content licensed under CC BY-NC 4.0.