Proof of `The Moser–Tardos theorem`

groundedproofs/Lax41Proofs/MoserTardos.lean · lax-41

What this proof establishes

no assumptions

Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.

Read the Lean proof on GitHub

Description

The Moser–Tardos witness-tree argument. An infinite table supplies every fresh sample used by the algorithm. Each resampling occurrence injects into a proper witness tree, the probability that a fixed tree occurs is the product of its event probabilities, and the branching-process estimate sums these products. Finiteness of that sum also yields a terminating table and hence an assignment avoiding all bad events.