= 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.
Back to article page
