40.07.09 · combinatorics / probabilistic-method

The Rödl Nibble and the Semi-Random Method

shipped3 tiersLean: none

Anchor (Master): Alon-Spencer 2016 *The Probabilistic Method* 4e Ch. 4 and the differential-equation method of Wormald 1995 *Ann. Appl. Probab.* 5 / 1999 *Lectures on Approximation and Randomized Algorithms*; Frankl-Rödl 1985 *Eur. J. Combin.* 6 (near-perfect matchings); Pippenger-Spencer 1989; Kahn 1996 *J. Combin. Theory Ser. A* 73 (asymptotic list-edge-colouring of hypergraphs); Ajtai-Komlós-Szemerédi 1980/1981 (the semi-random independent-set process and $R(3,k)$); Keevash 2014 (existence of designs) as the descendant of the nibble

Intuition Beginner

Suppose you must cover a huge board with tiles, where every tile blocks out a small fixed patch and no two tiles are allowed to overlap. You want to use as few tiles as possible and leave almost nothing uncovered. Placing tiles one at a time by careful hand-planning is hopeless when the board has billions of squares: a greedy choice early on can box you into a corner where the last patches refuse to fit. You would like a method that stays flexible to the very end.

The idea that works is to take many small random bites instead of one big plan. In each round you scatter a thin sprinkle of tiles at random across whatever space is still open. Most of them land cleanly; a few collide with each other, so you simply throw the colliding ones away. After this tidy-up, you have placed a modest batch with no overlaps, the open space has shrunk a little, and you repeat. Each bite is small enough that collisions are rare, and the leftover space keeps shrinking by a steady fraction.

Because every round removes the same fraction of what remains, after enough rounds the uncovered part is a tiny sliver. The surprise is that this "nibble" of random sprinkle plus clean-up, repeated, gets you within a hair of the best possible packing — something no rigid one-shot plan reliably achieves.

Visual Beginner

Picture the open space as a shrinking pool. At the start the whole pool is open. Each round you toss in a light handful of tiles: the green ones land without touching a neighbour and stay; the red ones overlap something and get scooped back out. What stays covers a slice of the pool, so the open pool shrinks before the next round.

Round	What you do	What happens to the open space
Start	nothing placed yet	the whole board is open
Each round	sprinkle a few random tiles, remove the colliding ones	open space shrinks by a steady fraction
After many rounds	keep repeating	only a tiny uncovered sliver is left

Because each round trims the same proportion, the open space decays the way a quantity halved again and again races toward zero — and the few survivors of every round add up to a near-perfect packing.

Worked example Beginner

We track how fast the open space shrinks when each round clears one third of what remains. Say the board starts with $9000$ open squares, and in every round the kept tiles cover one third of the currently open squares.

Step 1. After round one, one third of $9000$ is $3000$ , so $3000$ squares get covered and $9000 - 3000 = 6000$ stay open.

Step 2. After round two, one third of the $6000$ open squares is $2000$ , so $2000$ more get covered and $6000 - 2000 = 4000$ remain open.

Step 3. After round three, one third of $4000$ is about $1333$ , leaving roughly $4000 - 1333 = 2667$ open.

Step 4. Notice the pattern: each round multiplies the open count by $\frac{2}{3}$ . So after $r$ rounds the open count is about $9000 \times (2/3)^{r}$ . After $10$ rounds that is $9000 \times (2/3)^{10} \approx 9000 \times 0.017 \approx 156$ open squares — under $2%$ of the board still uncovered.

What this tells us: a fixed shrink fraction per round drives the leftover toward zero very fast, because repeated multiplication by a number below $1$ collapses quickly. The nibble never needs a clever global plan; the steady per-round bite does all the work, and the tiles kept across all rounds form the near-complete packing.

Check your understanding Beginner

Exercise (easy, multiple choice).

In the nibble method, why are the tiles sprinkled in many small rounds rather than placed all at once in a single large batch?

A. A single large batch is impossible to compute.

B. Small batches keep collisions rare, so most placed tiles can be kept after tidy-up.

C. The rules forbid placing more than one tile per round.

D. Small batches cover more squares per tile than large batches.

Hint

Think about what happens to overlaps when you throw in only a thin sprinkle versus a dense crowd.

Answer

B. A thin sprinkle rarely collides, so the clean-up discards few tiles and the round makes steady progress; a dense one-shot batch would collide everywhere and waste most of its tiles. Feedback-correct: keeping collisions rare per round is exactly what lets the method stay flexible to the end. Feedback-wrong: A and C invent constraints that are not there; D is backwards, since the per-tile efficiency is similar — the gain is in keeping more of them.

Formal definition Intermediate+

Throughout, $H = (V, E)$ is an $r$ -uniform hypergraph: $V$ is a finite vertex set and every edge $e \in E$ has exactly $r$ vertices. The degree $d (v)$ is the number of edges through $v$ , the maximum degree is $Δ = max_{v} d (v)$ , and the codegree $d (u, v)$ is the number of edges containing both $u$ and $v$ . The concentration apparatus the analysis rests on — the Doob exposure martingale and the Azuma / bounded-differences tail bound — is imported from 40.07.05 and applied, not reproved.

Definition (covering and packing numbers). Fix integers $n > k > ℓ \geq 1$ . A family $C$ of $k$ -subsets of $[n]$ is an $(n, k, ℓ)$ -covering if every $ℓ$ -subset of $[n]$ lies in at least one member of $C$ ; the covering number $C (n, k, ℓ)$ is the minimum size of such a family. A family $P$ of $k$ -subsets is an $(n, k, ℓ)$ -packing if every $ℓ$ -subset lies in at most one member; the packing number $D (n, k, ℓ)$ is the maximum size. Counting incidences between $k$ -sets and the $(ℓ n)$ target $ℓ$ -sets, with each $k$ -set covering $(ℓ k)$ of them, gives the fractional bounds $$ D(n,k,\ell) \le \frac{\binom{n}{\ell}}{\binom{k}{\ell}} \le C(n,k,\ell). $$ A Steiner system $S (ℓ, k, n)$ — when it exists — is simultaneously a packing and a covering meeting both bounds with equality (cross-ref 40.06.04).

Definition (semi-random / nibble process). A nibble is one round of: (i) select each surviving candidate independently with a small probability $ε$ (the bite size); (ii) among the selected candidates, activate those that conflict with no other selected or previously chosen candidate; (iii) add the activated candidates to the output, mark the targets they now satisfy as dead, and pass the still-unsatisfied targets and unconflicted candidates as the live set to the next round. Iterating with a fixed bite size for $T = O (ε^{- 1} lo g (1/ δ))$ rounds drives the live target fraction below $δ$ .

Definition (live-set trajectory). Let $L_{t}$ be the number of live targets and $Λ_{t}$ a typical live candidate's residual degree after round $t$ . The process is engineered so that, conditioned on the round- $t$ state, the expected one-step multiplicative change is $(1 - ε) (1 + o (1))$ for both, so the rescaled quantities follow the autonomous decay $x^{'} (τ) = - x (τ)$ in continuous time $τ = tε$ . Concentration of $L_{t}$ , $Λ_{t}$ about this trajectory is the content of the analysis.

Counterexamples to common slips Intermediate+

"One big random sample does the same job as many small nibbles." A single sample of the right total size produces conflicts at a constant rate, killing a constant fraction of its own picks; the per-round bite must be $o (1)$ so that the conflict probability within a round is $o (1)$ and the activated fraction is $(1 - o (1))$ of the selected.
"The nibble needs the hypergraph to be regular on the nose." Near-regularity, $d (v) = (1 \pm o (1)) D$ , suffices; the analysis only needs the live degrees to stay concentrated, not exactly equal.
"Small codegree is a convenience, not a hypothesis." It is essential. If two vertices share $Ω (D)$ edges, selecting one edge through the pair kills a constant fraction of the other's options in a single step, and the live degrees no longer decay smoothly — the trajectory description fails.
"The fractional bound is just a heuristic; the integral optimum could be far from it." Erdős and Hanani conjectured, and Rödl proved, that for coverings and packings the integral optimum is asymptotically the fractional bound. The gap is $o (1)$ in ratio, not a constant factor.

Key theorem with proof Intermediate+

The signature result is Rödl's theorem: the covering and packing numbers asymptotically meet the fractional bound, resolving the Erdős-Hanani conjecture. The proof is the prototype nibble, and the concentration estimates it needs are exactly the bounded-differences bounds of 40.07.05.

Theorem (Rödl 1985; Erdős-Hanani conjecture). Fix integers $k > ℓ \geq 1$ . As $n \to \infty$ , $$ C(n,k,\ell) = (1+o(1)),\frac{\binom{n}{\ell}}{\binom{k}{\ell}}, \qquad D(n,k,\ell) = (1+o(1)),\frac{\binom{n}{\ell}}{\binom{k}{\ell}}. $$ ^{[Rödl 1985]}

Proof. It suffices to prove the packing statement $D (n, k, ℓ) \geq (1 - o (1)) (ℓ n) / (ℓ k)$ ; the covering statement follows by a symmetric argument that adds a thin layer of $k$ -sets to cover the few leftover $ℓ$ -sets. Model the problem as a hypergraph $H$ whose vertices are the $(ℓ n)$ target $ℓ$ -sets and whose edges are the $k$ -sets, each edge being the $(ℓ k)$ -subset of $ℓ$ -sets it contains. Then $H$ is $(ℓ k)$ -uniform, every vertex (an $ℓ$ -set) has degree $D = (k - ℓ n - ℓ)$ (the $k$ -sets through a fixed $ℓ$ -set), and the codegree of two $ℓ$ -sets is $O ((k - ℓ - 1 n - ℓ - 1)) = o (D)$ since extending two $ℓ$ -sets to a common $k$ -set fixes more than $ℓ$ points. A packing is a matching in $H$ ; a near-perfect matching covers $(1 - o (1)) (ℓ n)$ vertices and uses $(1 - o (1)) (ℓ n) / (ℓ k)$ edges.

Run the nibble on $H$ with bite size $ε$ . In a round, select each live edge independently with probability $ε / D$ , so a fixed vertex is covered by some selected edge with probability $\approx ε$ . An edge is activated unless it shares a vertex with another selected edge; the expected number of competing selected edges through any of its $(ℓ k)$ vertices is $(ℓ k) \cdot D \cdot (ε / D) = (ℓ k) ε = O (ε)$ , so an edge is activated with probability $1 - O (ε)$ . Hence a vertex becomes dead in this round with probability $(1 - O (ε)) ε$ , and the live-vertex count satisfies $E [L_{t + 1} ∣ F_{t}] = (1 - ε + O (ε^{2})) L_{t}$ . The residual degree of a surviving vertex contracts by the same factor in expectation, using small codegree to ensure that no single selected edge removes more than $o (D)$ of a vertex's options.

Both $L_{t}$ and the live degrees are functions of the independent edge-selection coins of round $t$ , and altering one coin changes each by $O (1)$ relative to its scale; the bounded-differences inequality of 40.07.05 gives $L_{t + 1} = (1 - ε + O (ε^{2})) L_{t} (1 + o (1))$ and degrees $= (1 - ε + O (ε^{2})) (1 + o (1)) D_{t}$ with probability $1 - exp (- n^{Ω (1)})$ . Iterating $T = ⌈ ε^{- 1} lo g (1/ δ)⌉$ rounds and taking a union bound over rounds, with probability tending to $1$ the live-vertex fraction is at most $(1 - ε)^{T} + o (1) \leq δ + o (1)$ , while each round's activated edges form a partial matching and across all rounds they remain a single matching (an activated edge only touches live vertices, which are then killed). The matching covers $(1 - δ - o (1)) (ℓ n)$ vertices, hence has $(1 - δ - o (1)) (ℓ n) / (ℓ k)$ edges. Letting $δ \to 0$ slowly with $n$ gives the claim. $□$

Bridge. Rödl's theorem is the foundational reason the fractional relaxation of a packing problem is asymptotically achieved by an integral object: the nibble converts the greedy bound $(ℓ n) / (ℓ k)$ into a genuine matching by spending the slack as $o (1)$ losses spread thinly across many rounds, and this is exactly the move that the Pippenger-Spencer theorem of the Advanced results industrialises for arbitrary near-regular small-codegree hypergraphs. The construction builds toward the asymptotic existence of Steiner-system-like packings of 40.06.04, where the same matching-in-a-design-hypergraph reading appears again, and it generalises the deletion method of 40.07.02 from a single clean-up to an iterated one: where deletion removes defects once, the nibble removes a controlled fraction each round and re-bounds the survivors, so the bridge is that bounded-differences concentration from 40.07.05 is what makes the per-round bookkeeping survive iteration. Putting these together, the semi-random method is the first moment plus alteration run as a process rather than a single step, with concentration as the glue that keeps the expected trajectory honest at every round.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

In the hypergraph encoding of $D (n, k, ℓ)$ , show that the degree of every vertex (an $ℓ$ -set) is $D = (k - ℓ n - ℓ)$ and that the codegree of two distinct $ℓ$ -sets is $o (D)$ as $n \to \infty$ with $k, ℓ$ fixed.

Hint

A $k$ -set through a fixed $ℓ$ -set is chosen by adding $k - ℓ$ of the remaining $n - ℓ$ points. For two $ℓ$ -sets, a common $k$ -set must contain their union, of size $> ℓ$ .

Answer

A vertex is an $ℓ$ -set $L$ ; an edge through it is a $k$ -set $K \supseteq L$ , determined by choosing the other $k - ℓ$ points from $[n] ∖ L$ , so $d (L) = (k - ℓ n - ℓ) =: D \sim n^{k - ℓ} / (k - ℓ)!$ . For two distinct $ℓ$ -sets $L_{1}, L_{2}$ with $∣ L_{1} \cup L_{2} ∣ = ℓ + s$ , $s \geq 1$ , a common edge $K \supseteq L_{1} \cup L_{2}$ is chosen by adding $k - ℓ - s$ points from $[n] ∖ (L_{1} \cup L_{2})$ , so the codegree is $(k - ℓ - s n - ℓ - s) \sim n^{k - ℓ - s} / (k - ℓ - s)! = O (n^{k - ℓ - 1})$ . Hence codegree $/ D = O (n^{- 1}) = o (1)$ , the small-codegree hypothesis of the nibble. Rubric: full credit for the degree count $(k - ℓ n - ℓ)$ , the union-size $\geq ℓ + 1$ observation, and the ratio $O (1/ n) \to 0$ .

Exercise 4 (medium, symbolic).

In one nibble round on a $D$ -regular $r$ -uniform hypergraph, each edge is selected independently with probability $p = ε / D$ . Show that a fixed edge $e$ is activated (no selected edge shares a vertex with it) with probability $1 - O (ε)$ , and identify which hypothesis controls the error term.

Hint

Count the edges meeting $e$ : at most $r$ vertices, each in $D - 1$ other edges. Each is selected with probability $p$ . Use a union bound and $r D p = r ε$ .

Answer

Edge $e$ has $r$ vertices, each lying in at most $D - 1$ other edges, so at most $r (D - 1)$ edges meet $e$ (codegree overlaps only reduce this count). Each such edge is selected with probability $p = ε / D$ , so by a union bound the probability that some neighbour of $e$ is selected is at most $r (D - 1) p \leq r D p = r ε$ . Hence, conditioned on $e$ itself being selected, it is activated with probability at least $1 - r ε = 1 - O (ε)$ for fixed $r$ . The small-codegree hypothesis controls the second-order correction: without it, two vertices of $e$ could share many edges, making the union bound's overcount an undercount of the true correlation and spoiling the $1 - O (ε)$ estimate's uniformity across edges. Rubric: full credit for the neighbour count $\leq r D$ , the union bound giving $1 - r ε$ , and naming small codegree as the hypothesis behind uniformity.

Exercise 5 (medium, symbolic).

Let $L_{t}$ be the live-vertex count after round $t$ , with $E [L_{t + 1} ∣ F_{t}] = (1 - ε^{'}) L_{t}$ where $ε^{'} = ε (1 + o (1))$ . Assuming each round's contribution concentrates, show that after $T = ⌈ ε^{- 1} ln (1/ δ)⌉$ rounds the expected live fraction is at most $δ (1 + o (1))$ .

Hint

Iterate the expectation to get $(1 - ε^{'})^{T}$ , then use $1 - ε^{'} \leq e^{- ε^{'}}$ and $T ε^{'} \geq ln (1/ δ)$ .

Answer

Taking expectations and iterating the one-step contraction, $E [L_{T}] / L_{0} = \prod_{t = 0}^{T - 1} (1 - ε^{'}) = (1 - ε^{'})^{T}$ . Using $1 - ε^{'} \leq e^{- ε^{'}}$ , $(1 - ε^{'})^{T} \leq e^{- ε^{'} T}$ . With $T = ⌈ ε^{- 1} ln (1/ δ)⌉$ and $ε^{'} = ε (1 + o (1))$ , we get $ε^{'} T \geq (1 + o (1)) ln (1/ δ)$ , so $e^{- ε^{'} T} \leq δ^{1 + o (1)} = δ (1 + o (1))$ for fixed $δ$ . Hence the expected live fraction is at most $δ (1 + o (1))$ . The bounded-differences inequality of 40.07.05 upgrades this expectation statement to a whp-statement, since $L_{t}$ changes by $O (1)$ per selection coin. Rubric: full credit for the product form $(1 - ε^{'})^{T}$ , the exponential bound, and the substitution $T ε^{'} \geq ln (1/ δ)$ .

Exercise 7 (hard, symbolic).

State the Pippenger-Spencer theorem and deduce the near-perfect-matching corollary: a nearly-regular $r$ -uniform hypergraph with maximum codegree $o (D)$ has a matching covering $(1 - o (1)) ∣ V ∣$ vertices.

Hint

Pippenger-Spencer bounds the chromatic index $χ^{'} (H) = (1 + o (1)) D$ . A proper edge-colouring partitions the edges into matchings; the largest of the $(1 + o (1)) D$ colour classes must be big.

Answer

Theorem (Pippenger-Spencer). If $H$ is $r$ -uniform on $N$ vertices with every degree $(1 \pm o (1)) D$ and maximum codegree $o (D)$ , then $χ^{'} (H) = (1 + o (1)) D$ , where $χ^{'} (H)$ is the least number of matchings partitioning $E (H)$ . Corollary. The number of edges is $∣ E ∣ = (1 \pm o (1)) N D / r$ (sum of degrees over $r$ ), and they split into $(1 + o (1)) D$ matchings, so the average matching has $∣ E ∣/ χ^{'} = (1 \pm o (1)) N / r$ edges, covering $(1 \pm o (1)) N$ vertices; the largest class covers at least the average, giving a matching on $(1 - o (1)) N$ vertices. The proof of the theorem is the nibble run on edges-as-objects with $D$ available colours, each round colouring a random unconflicted slice and tracking the live (uncoloured) edges and available palette by 40.07.05 concentration. Rubric: full credit for the correct $χ^{'} = (1 + o (1)) D$ statement with both hypotheses, the edge count $N D / r$ , and the averaging step extracting a near-perfect matching.

Exercise 8 (hard, short-answer).

Explain in one paragraph why the bite size $ε$ must satisfy $ε \to 0$ (many rounds) rather than $ε = Θ (1)$ (few rounds), and what role concentration plays in making the limit rigorous.

Hint

The activated fraction is $1 - O (ε)$ per round. If $ε$ is a constant, a constant fraction of picks self-conflict and are wasted, and the per-round loss no longer vanishes.

Answer

If the bite size $ε$ is a constant, then within a single round a constant fraction $O (ε)$ of the selected candidates collide with one another and are discarded, so the round's loss relative to the ideal geometric contraction is a constant, not $o (1)$ — accumulated over the $O (1)$ rounds needed to finish, these constant losses leave a constant gap below the fractional bound, and the method achieves only $c \cdot (ℓ n) / (ℓ k)$ for some $c < 1$ . Taking $ε \to 0$ makes the per-round self-conflict probability $O (ε) = o (1)$ , so each round is $(1 - o (1))$ -efficient; the price is $T = Θ (ε^{- 1} lo g (1/ δ))$ rounds, and the cumulative multiplicative error is $(1 + o (1))^{T}$ , which stays $1 + o (1)$ only because the per-round error is $o (ε)$ , i.e. summable. Concentration is what makes the limit rigorous: the expected trajectory $L_{t} \approx (1 - ε)^{t} L_{0}$ is only an average, and over $T$ rounds the deviations could in principle compound; the bounded-differences inequality of 40.07.05 bounds each round's deviation by $exp (- n^{Ω (1)})$ , so a union bound over all $T$ rounds keeps the entire trajectory within $(1 + o (1))$ of its expectation with probability tending to $1$ . Rubric: full credit for the constant-loss argument against $ε = Θ (1)$ , the $ε^{- 1}$ round count, and the role of concentration plus union bound in controlling the whole trajectory.

Advanced results Master

The nibble matures into a general theory: the Pippenger-Spencer and Kahn theorems turn fractional relaxations into integral colourings for arbitrary near-regular small-codegree hypergraphs, the Ajtai-Komlós-Szemerédi process extracts large independent sets from sparse graphs, and Wormald's differential-equation method gives the systematic trajectory framing that makes "expected change per round" a rigorous description of the whole evolution.

Theorem 1 (Pippenger-Spencer chromatic index). Let $H$ be an $r$ -uniform hypergraph on $N$ vertices, $r$ fixed, with all degrees $(1 \pm o (1)) D$ and maximum codegree $o (D)$ as $D \to \infty$ . Then the chromatic index satisfies $χ^{'} (H) = (1 + o (1)) D$ ^{[Pippenger-Spencer 1989]}. The lower bound $χ^{'} \geq Δ = (1 + o (1)) D$ is immediate; the content is that the random-greedy semi-random colouring matches it, so the fractional edge-colouring bound is asymptotically integral. Reading one colour class at a time yields the near-perfect matching corollary that subsumes Rödl's theorem: the Erdős-Hanani hypergraph is near-regular with codegree $O (1/ n) \cdot D$ , so a matching covers $(1 - o (1))$ of its vertices.

Theorem 2 (Kahn's asymptotic list-edge-colouring). Under the same near-regularity and small-codegree hypotheses, the list chromatic index is also $(1 + o (1)) D$ : if each edge $e$ is given an arbitrary list $L (e)$ of $(1 + o (1)) D$ admissible colours, a proper colouring choosing each edge's colour from its own list still exists ^{[Kahn 1996]}. The proof is a multi-round semi-random colouring in which each round assigns a random admissible colour to a slice of edges and retains the conflict-free assignments, with an entropy/concentration clean-up tracking the shrinking lists. This is the principle that asymptotic goodness of the fractional relaxation forces integral goodness, in its sharpest combinatorial form, and it implies the dense cases of the List-Edge-Colouring and Goldberg-Seymour conjectures.

Theorem 3 (Ajtai-Komlós-Szemerédi; $R (3, k)$ ). The semi-random method applied to the independent-set problem in triangle-free graphs of average degree $d$ produces an independent set of size $(1 - o (1)) \frac{n l n d}{d}$ , beating the greedy $n / d$ by the factor $ln d$ . Applied to the Ramsey graph, this yields $R (3, k) = O (k^{2} / lo g k)$ , which with Kim's matching lower bound (also semi-random, the triangle-free process) gives $R (3, k) = Θ (k^{2} / lo g k)$ . The process reveals vertices in random order, greedily building an independent set while a concentration argument shows the surviving "uncoloured" neighbourhood shrinks along the predicted trajectory — the independent-set analogue of the live-degree decay in Rödl's proof.

Theorem 4 (Wormald's differential-equation method). Let $(Y^{(m)})_{m \geq 0}$ be a random process on a state space, with bounded one-step changes $∣ Y_{i}^{(m + 1)} - Y_{i}^{(m)} ∣ \leq β$ and conditional expected increment $E [Y_{i}^{(m + 1)} - Y_{i}^{(m)} ∣ F_{m}] = f_{i} (m / N, Y^{(m)} / N) + o (1)$ for a Lipschitz $f$ . Then, with the scaling $y_{i} (τ) = Y_{i}^{(τ N)} / N$ , the process satisfies $y_{i} (τ) = \overset{y}{^}_{i} (τ) + o (1)$ whp, uniformly until $τ$ leaves the domain, where $\hat{y}$ solves $\overset{y}{^}_{i}^{'} (τ) = f_{i} (τ, \hat{y})$ , $\hat{y} (0) = Y^{(0)} / N$ ^{[Wormald 1995]}. The proof packages the bounded-differences inequality of 40.07.05: the martingale of the rescaled trajectory has $O (β / N)$ increments, so over a window of $O (N)$ steps it stays within $o (1)$ of the integrated drift by Azuma plus a Grönwall comparison. The nibble's live-set sizes are precisely such bounded-step processes, and their decay $x^{'} (τ) = - x (τ)$ is the autonomous system the method certifies.

Theorem 5 (designs as the descendant; Keevash). The asymptotic existence of designs — that for fixed $k, ℓ$ and all large $n$ meeting the divisibility conditions there is an exact Steiner system $S (ℓ, k, n)$ — was open for over a century and resolved by Keevash (2014) via randomised algebraic constructions, a far-reaching descendant of the nibble in which the semi-random matching is corrected to an exact one by an algebraic absorber ^{[Alon-Spencer 2016]}. Rödl's nibble supplies the $(1 - o (1))$ -packing that Keevash's absorption upgrades to a perfect design; Glock-Kühn-Lo-Osthus gave an independent absorption proof. The lineage Erdős-Hanani conjecture $\to$ Rödl nibble $\to$ Pippenger-Spencer $\to$ Keevash is the through-line from "approximate packing" to "exact design."

Synthesis. The semi-random method is the deletion method of 40.07.02 iterated as a process, with bounded-differences concentration from 40.07.05 as the foundational reason the iteration is honest: each nibble removes a $(1 - o (1)) ε$ -fraction of the live objects in expectation, and because the round's contribution is a bounded-difference function of independent selection coins, it concentrates around that expectation with $exp (- n^{Ω (1)})$ error, so a union bound over $O (ε^{- 1} lo g (1/ δ))$ rounds pins the whole trajectory $L_{t} \approx (1 - ε)^{t} L_{0}$ to its mean. This is exactly the move that proves Rödl's resolution of the Erdős-Hanani conjecture, and the Pippenger-Spencer theorem generalises it from packings to the chromatic index of every near-regular small-codegree hypergraph, with Kahn's theorem sharpening it to the list setting — three faces of the central insight that asymptotic fractional optimality forces asymptotic integral optimality. The differential-equation method is dual to the round-by-round bookkeeping: where the nibble counts discrete rounds, Wormald reads the same data as the autonomous flow $x^{'} (τ) = - x (τ)$ and certifies the discrete process tracks the continuous solution, which is the bridge from the heuristic "expected change per step" to a theorem. Putting these together, the lineage from the Ajtai-Komlós-Szemerédi $R (3, k)$ bound through Rödl and Pippenger-Spencer to Keevash's designs is one technique — build a near-optimal structure by many small random rounds with concentration-controlled clean-up — applied at successively higher resolution, and the absorption method that finishes the job is what converts the nibble's $(1 - o (1))$ -approximation into the long-sought exact object.

Full proof set Master

Proposition 1 (one-round live-vertex contraction). Let $H$ be $D$ -regular $r$ -uniform with maximum codegree $C = o (D)$ , and run one nibble round selecting each edge independently with probability $p = ε / D$ . For a fixed live vertex $v$ , the probability it becomes dead this round is $ε (1 - O (ε) - O (C / D))$ .

Proof. Vertex $v$ dies if at least one of its $D$ edges is activated. Let $A_{v}$ be the event that some edge through $v$ is selected: $Pr (A_{v}) = 1 - (1 - p)^{D} = 1 - (1 - ε / D)^{D} = ε - ε^{2} /2 + O (ε^{3}) = ε (1 - O (ε))$ . Conditioned on a specific edge $e ∋ v$ being selected, $e$ is activated unless a competing edge sharing one of $e$ 's $r$ vertices is also selected; the number of such competitors is at most $r (D - 1) - (codegree overcount)$ , each selected with probability $p$ , so by inclusion-exclusion the activation probability is $1 - r (D - 1) p + O ((r D p)^{2}) = 1 - r ε + O (ε^{2})$ . The codegree enters because two vertices of $e$ may share up to $C$ edges, double-counted in $r (D - 1)$ ; correcting this shifts the estimate by $O (r C p) = O (εC / D)$ . Combining, $v$ dies with probability $ε (1 - O (ε)) \cdot (1 - r ε + O (ε^{2}) + O (εC / D)) = ε (1 - O (ε) - O (C / D))$ . $□$

Proposition 2 (concentration of the live count). With $H, p$ as above and $L_{t}$ the number of live vertices after round $t$ , conditioned on $F_{t}$ , $L_{t + 1}$ satisfies $Pr (∣ L_{t + 1} - E [L_{t + 1} ∣ F_{t}] ∣ \geq λ) \leq 2 exp (- 2 λ^{2} / (r^{2} M_{t}))$ , where $M_{t}$ is the number of edges selectable in round $t + 1$ .

Proof. Condition on $F_{t}$ , fixing the live hypergraph. The randomness of round $t + 1$ is the independent selection coin $ξ_{e} \in {0, 1}$ for each of the $M_{t}$ live edges. Write $L_{t + 1} = g (ξ)$ , a function of these independent coins. Flipping one coin $ξ_{e}$ changes the activation status of $e$ and of the edges meeting $e$ , altering the set of newly-dead vertices by at most the $\leq r$ vertices of $e$ plus the vertices of edges sharing one of them; a careful accounting (an activated $e$ kills exactly its $r$ live vertices, and toggling $e$ can de-activate at most its immediate neighbours, each contributing $\leq r$ vertices already counted) bounds the change in $L_{t + 1}$ by $c_{e} = r$ uniformly. McDiarmid's bounded-differences inequality of 40.07.05 applied to $g$ with $\sum_{e} c_{e}^{2} = r^{2} M_{t}$ gives $Pr (∣ L_{t + 1} - E [L_{t + 1} ∣ F_{t}] ∣ \geq λ) \leq 2 exp (- 2 λ^{2} / (r^{2} M_{t}))$ . $□$

Proposition 3 (trajectory bound over all rounds). For $ε \to 0$ slowly and $T = ⌈ ε^{- 1} ln (1/ δ)⌉$ , with probability $1 - o (1)$ the live fraction after $T$ rounds is at most $δ (1 + o (1))$ .

Proof. By Proposition 1, $E [L_{t + 1} ∣ F_{t}] = (1 - ε (1 - o (1))) L_{t}$ as long as $L_{t} = n^{Ω (1)}$ (so degrees stay $n^{Ω (1)}$ and the codegree correction $C / D$ remains $o (1)$ ). Set $λ_{t} = L_{t}^{2/3}$ in Proposition 2; since $M_{t} \leq n L_{t} \leq n^{O (1)}$ and $λ_{t}^{2} = L_{t}^{4/3} \geq n^{Ω (1)} \cdot M_{t} / n^{O (1)}$ in the regime $L_{t} \geq n^{c}$ , the tail is $exp (- n^{Ω (1)})$ . Thus, with failure probability $exp (- n^{Ω (1)})$ per round, $L_{t + 1} = (1 - ε (1 - o (1))) L_{t} (1 \pm L_{t}^{- 1/3})$ . A union bound over the $T = n^{o (1)}$ rounds (for $ε \geq n^{- o (1)}$ ) keeps every round on track with probability $1 - T exp (- n^{Ω (1)}) = 1 - o (1)$ . Multiplying the per-round factors, $L_{T} = L_{0} \prod_{t < T} (1 - ε (1 - o (1))) (1 \pm L_{t}^{- 1/3}) = L_{0} (1 - ε)^{T} (1 + o (1))$ , and $(1 - ε)^{T} \leq e^{- εT} \leq δ$ by the choice of $T$ . The accumulated relative error $\prod (1 \pm L_{t}^{- 1/3})$ is $1 + o (1)$ because $\sum_{t} L_{t}^{- 1/3}$ is dominated by its smallest terms, which stay $n^{- Ω (1)}$ until the process is stopped at live fraction $δ$ . Hence $L_{T} \leq δ (1 + o (1)) L_{0}$ whp. $□$

Proposition 4 (Rödl packing lower bound). For fixed $k > ℓ \geq 1$ , $D (n, k, ℓ) \geq (1 - o (1)) (ℓ n) / (ℓ k)$ .

Proof. Encode as the $(ℓ k)$ -uniform hypergraph $H$ on the $(ℓ n)$ vertices (the $ℓ$ -sets) whose edges are the $k$ -sets. By Exercise 3, $H$ is $D$ -regular with $D = (k - ℓ n - ℓ)$ and maximum codegree $O (D / n) = o (D)$ . Run the nibble; the activated edges across all rounds form a matching $M$ (an edge is activated only on currently-live vertices, which it then kills, so no two activated edges share a vertex). By Proposition 3, after $T = ⌈ ε^{- 1} ln (1/ δ)⌉$ rounds at most $δ (1 + o (1)) (ℓ n)$ vertices remain live, so $M$ covers $(1 - δ - o (1)) (ℓ n)$ vertices and therefore contains $(1 - δ - o (1)) (ℓ n) / (ℓ k)$ edges, each a $k$ -set, no two sharing an $ℓ$ -set — an $(n, k, ℓ)$ -packing of that size. Sending $δ \to 0$ slowly with $n$ gives $D (n, k, ℓ) \geq (1 - o (1)) (ℓ n) / (ℓ k)$ . The matching upper bound $D (n, k, ℓ) \leq (ℓ n) / (ℓ k)$ is the fractional count, so equality holds asymptotically. $□$

Proposition 5 (covering from packing). $C (n, k, ℓ) \leq (1 + o (1)) (ℓ n) / (ℓ k)$ .

Proof. Take the near-perfect packing $P$ of Proposition 4, covering all but a set $U$ of at most $o (1) (ℓ n)$ $ℓ$ -sets. Cover each remaining $ℓ$ -set of $U$ by any single $k$ -set containing it (one exists as $k > ℓ$ ): this adds at most $∣ U ∣ = o (1) (ℓ n) \leq o (1) (ℓ n) / (ℓ k) \cdot (ℓ k) = o ((ℓ n) / (ℓ k))$ extra $k$ -sets once the bound $∣ U ∣ = o ((ℓ n))$ is divided through, since each added $k$ -set still covers $(ℓ k)$ targets and the surplus is lower order. The union $P \cup (patch)$ is an $(n, k, ℓ)$ -covering of size $(1 + o (1)) (ℓ n) / (ℓ k)$ , so $C (n, k, ℓ)$ is at most this. With the fractional lower bound $C \geq (ℓ n) / (ℓ k)$ , equality holds asymptotically. $□$

Connections Master

The round-by-round control that makes the nibble rigorous is the bounded-differences (Azuma / McDiarmid) concentration of 40.07.05: each round's newly-dead-vertex count is a bounded-difference function of that round's independent selection coins, so it concentrates around the contraction of Proposition 1 with $exp (- n^{Ω (1)})$ error, and the foundational reason the iterated process stays on its expected trajectory is the union bound over rounds that this exponential tail permits. Without that concentration the expected geometric decay would be only an average, and the cumulative deviation across $Θ (ε^{- 1} lo g n)$ rounds could destroy the $(1 + o (1))$ guarantee.
The semi-random method is the deletion / alteration method of 40.07.02 run as a process rather than a single step: where deletion samples once and removes the rare defects, the nibble removes a controlled $(1 - o (1)) ε$ -fraction each round and re-bounds the survivors, and the first-moment expectation calculations of 40.07.01 supply the per-round expected contraction that the alteration then realises. The Erdős-Hanani resolution is exactly this iterated alteration applied to the design hypergraph.
The packings the nibble produces are the asymptotic version of the exact combinatorial designs of 40.06.04: a Steiner system $S (ℓ, k, n)$ is a perfect packing-and-covering meeting the fractional bound exactly, and the nibble shows that even when no exact system exists the optimum is within $(1 + o (1))$ of the divisibility bound — the approximate statement that Keevash's absorption later upgraded to the exact existence of designs.
The semi-random independent-set process behind the Ajtai-Komlós-Szemerédi bound $R (3, k) = Θ (k^{2} / lo g k)$ is the Ramsey-theoretic face of the same machine, complementing the discrepancy-theoretic control of structured deviations in 40.07.08: where discrepancy measures how far a set system departs from its ideal balanced colouring, the nibble manufactures a near-ideal sparse structure whose deviations from the expected trajectory are held to $o (1)$ by concentration, and both are quantitative refinements of the probabilistic existence arguments of this chapter.

Historical & philosophical context Master

The covering-and-packing question was posed by Paul Erdős and Haim Hanani in 1963, who conjectured that the integral covering and packing numbers $C (n, k, ℓ)$ and $D (n, k, ℓ)$ approach the fractional (divisibility) bound $(ℓ n) / (ℓ k)$ in ratio as $n \to \infty$ , and proved it for the boundary cases $ℓ = k - 1$ by elementary means. The general conjecture resisted for two decades until Vojtěch Rödl's 1985 paper in the European Journal of Combinatorics ^{[Rödl 1985]}, which introduced the iterated random-greedy "nibble" and a second-moment concentration argument to construct near-optimal packings directly; the technique was immediately recognised as a new general tool and the name Rödl nibble attached to it. Frankl and Rödl gave the near-perfect-matching formulation in the same period.

Nicholas Pippenger and Joel Spencer's 1989 paper ^{[Pippenger-Spencer 1989]} in the Journal of Combinatorial Theory abstracted the method to the chromatic index of nearly-regular small-codegree uniform hypergraphs, and Jeff Kahn's 1996 paper ^{[Kahn 1996]} extended it to the list setting, establishing that asymptotic fractional optimality forces integral optimality across a wide class. Noga Wormald ^{[Wormald 1995]} systematised the trajectory analysis as the differential-equation method, identifying the autonomous Lipschitz system whose solution the bounded-step process tracks. The earlier Ajtai-Komlós-Szemerédi semi-random independent-set process (1980-81) had already used the same philosophy to prove $R (3, k) = O (k^{2} / lo g k)$ , later matched below by Kim's triangle-free process. The line culminates in Keevash's 2014 randomised-algebraic resolution of the existence of designs, which combines the nibble with an absorption step to convert near-perfect packings into exact Steiner systems, settling a question open since the nineteenth century ^{[Alon-Spencer 2016]}.

Bibliography Master

@article{rodl1985,
  author  = {R\"{o}dl, Vojt\v{e}ch},
  title   = {On a packing and covering problem},
  journal = {European Journal of Combinatorics},
  volume  = {6},
  number  = {1},
  pages   = {69--78},
  year    = {1985}
}

@article{erdoshanani1963,
  author  = {Erd{\H{o}}s, Paul and Hanani, Haim},
  title   = {On a limit theorem in combinatorical analysis},
  journal = {Publicationes Mathematicae Debrecen},
  volume  = {10},
  pages   = {10--13},
  year    = {1963}
}

@article{pippengerspencer1989,
  author  = {Pippenger, Nicholas and Spencer, Joel},
  title   = {Asymptotic behavior of the chromatic index for hypergraphs},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {51},
  number  = {1},
  pages   = {24--42},
  year    = {1989}
}

@article{frankrodl1985,
  author  = {Frankl, Peter and R\"{o}dl, Vojt\v{e}ch},
  title   = {Near perfect coverings in graphs and hypergraphs},
  journal = {European Journal of Combinatorics},
  volume  = {6},
  number  = {4},
  pages   = {317--326},
  year    = {1985}
}

@article{kahn1996,
  author  = {Kahn, Jeff},
  title   = {Asymptotically good list-colorings},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {73},
  number  = {1},
  pages   = {1--59},
  year    = {1996}
}

@article{wormald1995,
  author  = {Wormald, Nicholas C.},
  title   = {Differential equations for random processes and random graphs},
  journal = {Annals of Applied Probability},
  volume  = {5},
  number  = {4},
  pages   = {1217--1235},
  year    = {1995}
}

@article{aks1980,
  author  = {Ajtai, Mikl\'{o}s and Koml\'{o}s, J\'{a}nos and Szemer\'{e}di, Endre},
  title   = {A note on Ramsey numbers},
  journal = {Journal of Combinatorial Theory, Series A},
  volume  = {29},
  number  = {3},
  pages   = {354--360},
  year    = {1980}
}

@article{keevash2014,
  author  = {Keevash, Peter},
  title   = {The existence of designs},
  journal = {arXiv:1401.3665},
  year    = {2014}
}

@book{molloyreed2002,
  author    = {Molloy, Michael and Reed, Bruce},
  title     = {Graph Colouring and the Probabilistic Method},
  publisher = {Springer},
  year      = {2002}
}

@book{alonspencer2016,
  author    = {Alon, Noga and Spencer, Joel H.},
  title     = {The Probabilistic Method},
  edition   = {4},
  publisher = {Wiley-Interscience},
  year      = {2016}
}

Prerequisites

40.07.05

Tier anchors

beginner: Alon-Spencer 2016 *The Probabilistic Method* 4e (Wiley) Ch. 4 (the Rödl nibble) and the survey framing in Molloy-Reed 2002 *Graph Colouring and the Probabilistic Method* (Springer) Part III; a 'take many small random bites and tidy up after each' analogy for how a near-perfect cover is assembled a little at a time
intermediate: Alon-Spencer 2016 *The Probabilistic Method* 4e Ch. 4 §4.7 (the Rödl nibble proof of the Erdős-Hanani conjecture) and the Pippenger-Spencer matching theorem; Pippenger-Spencer 1989 *J. Combin. Theory Ser. A* 51 (asymptotics of the chromatic index of uniform hypergraphs); Rödl 1985 *European J. Combin.* 6 (on a packing and covering problem of Erdős and Hanani)
master: Alon-Spencer 2016 *The Probabilistic Method* 4e Ch. 4 and the differential-equation method of Wormald 1995 *Ann. Appl. Probab.* 5 / 1999 *Lectures on Approximation and Randomized Algorithms*; Frankl-Rödl 1985 *Eur. J. Combin.* 6 (near-perfect matchings); Pippenger-Spencer 1989; Kahn 1996 *J. Combin. Theory Ser. A* 73 (asymptotic list-edge-colouring of hypergraphs); Ajtai-Komlós-Szemerédi 1980/1981 (the semi-random independent-set process and $R(3,k)$); Keevash 2014 (existence of designs) as the descendant of the nibble

References

Alon, N. & Spencer, J. H. — The Probabilistic Method · Wiley, 4th edition (2016). Chapter 4, "The Second Moment" and the dedicated treatment of the Rödl nibble, develops the semi-random method: a near-optimal structure is built in many rounds, each round selecting a small random "nibble" of the remaining candidates and cleaning up the conflicts it creates, with martingale/bounded-differences concentration controlling the number of "live" (still-available) elements from round to round. The flagship application is Rödl's theorem resolving the Erdős-Hanani conjecture: the covering number $C(n,k,\ell)$ and the packing number $D(n,k,\ell)$ both satisfy $C(n,k,\ell), D(n,k,\ell) = (1+o(1))\binom{n}{\ell}/\binom{k}{\ell}$, the fractional (greedy) bound, as $n \to \infty$. The chapter states the Pippenger-Spencer theorem on the chromatic index of nearly-regular uniform hypergraphs with small codegree and sketches the iterated random-greedy analysis.
Rödl, V. — On a packing and covering problem · *European Journal of Combinatorics* 6 (1985), 69-78. Resolution of the 1963 Erdős-Hanani conjecture: for fixed $k > \ell \ge 2$, the maximum number $D(n,k,\ell)$ of $k$-subsets of $[n]$ pairwise intersecting in fewer than $\ell$ points (an $\ell$-packing) and the minimum number $C(n,k,\ell)$ of $k$-subsets covering every $\ell$-subset both approach the divisibility (fractional) bound $\binom{n}{\ell}/\binom{k}{\ell}$ in ratio as $n \to \infty$. The proof introduces the "nibble": repeatedly select a sparse random subfamily of the surviving $k$-sets, retain those with no $\ell$-conflict, delete the $\ell$-sets they now cover, and iterate; a second-moment / concentration argument shows the uncovered $\ell$-sets and the surviving degrees stay close to their expected geometric decay.
Pippenger, N. & Spencer, J. — Asymptotic behavior of the chromatic index for hypergraphs · *Journal of Combinatorial Theory, Series A* 51 (1989), 24-42. If an $r$-uniform hypergraph $H$ on $N$ vertices is nearly regular — every vertex in $(1\pm o(1))D$ edges — with maximum codegree $o(D)$ (every pair of vertices in $o(D)$ common edges), then its chromatic index satisfies $\chi'(H) = (1+o(1))D$, matching the trivial lower bound $\Delta(H)$. The proof refines Rödl's nibble: the edges are properly coloured in $O(1)$ passes of random-greedy colour assignment with clean-up, the surviving uncoloured edges and the available palette tracked by concentration. The companion near-perfect matching statement — such an $H$ has a matching covering $(1-o(1))N$ vertices — is the $\chi' \approx D$ statement read one colour class at a time.
Wormald, N. C. — Differential equations for random processes and random graphs · *Annals of Applied Probability* 5 (1995), 1217-1235, and the lecture notes *The Differential Equation Method for Random Graph Processes and Greedy Algorithms* (1999). The systematic framing of the nibble and other bounded-step random processes: when a sequence of random variables changes by $O(1)$ per step and has conditional expected one-step increment given by a Lipschitz function $f(t, \mathbf{x})$ of the rescaled trajectory, the process concentrates (via Azuma/bounded differences) around the solution of the autonomous system $x_i'(t) = f_i(t, \mathbf{x})$. The nibble's live-set sizes follow such trajectories, and the differential-equation method converts the heuristic "expected change per round" into a rigorous whp-statement of the whole evolution.
Kahn, J. — Asymptotically good list-colorings · *Journal of Combinatorial Theory, Series A* 73 (1996), 1-59. The list analogue of Pippenger-Spencer: a nearly-regular, small-codegree $r$-uniform (multi)hypergraph has list-chromatic index asymptotic to its maximum degree, so the fractional-relaxation bound is achieved integrally even when each edge has its own palette. The proof is a multi-round semi-random colouring with an entropy/concentration clean-up, and it subsumes the asymptotic Goldberg-Seymour and List-Edge-Colouring conjectures for the dense regime.

Estimated time

beginner: 18m
intermediate: 47m
master: 90m