Semi-random method

The semi-random method constructs a combinatorial object in many small random rounds, discarding incompatible proposals and updating the remaining constraints after each round. Independent proposals give calculable expected changes; concentration and deterministic corrections preserve the statistics needed for subsequent rounds. Unlike a single random sample, this combines repeated randomness with a structured evolving state. The Rödl nibble is a matching in a hypergraph version of this method.

For a nearly $D$-regular $s$-uniform hypergraph, sample each edge independently with probability $\alpha /D$, where $\alpha$ is small. Retain the isolated sampled edges as a matching in a hypergraph, and delete every vertex incident to any sampled edge before the next round. A vertex survives with probability $(1-\alpha /D{)}^{d(v)}\approx e^{-\alpha }$; a sampled edge meets another sampled edge with probability at most $s\alpha (1+o(1))$. Thus accepted edges cover order $\alpha$ of the vertices and collision waste is order ${\alpha }^2$. Small hypergraph codegrees control the overlap terms in residual-degree calculations. Repeating a bounded number of rounds while tracking near-regularity is the characteristic Rödl nibble mechanism.