Lovász local lemma

The Lovász local lemma gives conditions under which a finite family of events can all be avoided when each event depends on only a limited number of others.

Dependency graph: A graph encoding which pairs of events or variables can influence one another. The lemma uses graph neighborhoods to specify which events may depend on each event.
Probabilistic method: A proof technique that establishes existence by showing that a randomly chosen object has positive probability of a desired property. The local lemma strengthens this method when bad events are dependent but locally constrained.
Paul Erdős: A Hungarian mathematician whose work shaped modern combinatorics and number theory. Erdős introduced the lemma with László Lovász to prove a graph-coloring result.
Lovász local lemma (symmetric version): A form of the local lemma with uniform bounds on event probabilities and dependency degrees. Its compact threshold is convenient when all events have comparable probabilities and neighborhoods.
Event: A subset of outcomes in a probability space, to which a probability is assigned. The lemma bounds the probabilities of events whose simultaneous avoidance is sought.
Graph coloring: An assignment of colors to graph vertices, often required to give adjacent vertices different colors. Coloring proofs encode local violations as events and use the lemma to avoid them.
László Lovász: A Hungarian mathematician known for major contributions to combinatorics, optimization, and theoretical computer science. Lovász co-developed the lemma and gave it its name.
Shearer’s lemma: A sharp criterion for the Lovász local lemma expressed through the independence polynomial of a dependency graph. It characterizes the optimal probability region for the abstract dependency-graph setting.
Probability space: A sample space equipped with a collection of events and a probability measure. The lemma's events and conditional probabilities are defined within a probability space.
Hypergraph coloring: A coloring of a hypergraph's vertices that avoids specified monochromatic edges or other forbidden color patterns. The lemma yields existence bounds for colorings that avoid monochromatic hyperedges.

Linked from 2 pages

Erdős–Faber–Lovász conjectureRelated: Its versions support coloring arguments where each bad event depends on only a limited set of others.