= Rödl nibble
{c}
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.
Back to article page
