Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble

Statement

"Semi-random method" is the standard alternate name for the Rödl nibble. The two terms denote the same technique: build a large near-perfect combinatorial structure (matching, packing/covering design, edge-colouring, pseudorandom set) not by a single random choice (fully random) and not by a deterministic greedy algorithm (fully determined), but by repeated small random selections interleaved with concentration arguments — a controlled sequence of "nibbles" out of the search space, each analyzed via second-moment / Lovász Local Lemma / Talagrand-type concentration before the next nibble is taken. Molloy & Reed's textbook *Graph Colouring and the Probabilistic Method* (Algorithms and Combinatorics 23, Springer 2002) devotes a chapter explicitly titled "The Semi-Random Method" to exactly this Rödl-nibble machinery and its edge-/list-colouring descendants, confirming the terms are synonyms in the literature, not two different tools.

**The full precise statement — the Erdős–Hanani conjecture, its 1985 resolution by Rödl, the modern quantified Kostochka–Rödl/Vu/Gould–Kelly bounds, and the Pippenger–Spencer edge-colouring generalization — is written out in full, with inline citations, in Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings.** This page intentionally does not re-derive that content; see that page's ## Statement section for the exact inequalities.

Facts

- Same technique, two names, one canonical page. All primary and secondary sources for this technique (V. Rödl 1985; Frankl–Rödl 1985; Pippenger–Spencer 1989; Kim 1995; Kostochka–Rödl 1997; Vu 2000; Molloy–Reed 2000; Ford–Green–Konyagin–Maynard–Tao 2018; Gould–Kelly 2025 arXiv:2511.11375) are catalogued with full citation strings in Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings's ## Facts and ## Statement sections — consult that page rather than this one for citations. - Why "semi-random." The name contrasts the method with (a) a *fully random* one-shot construction (e.g. a single random subset, analyzed by first/second moment) and (b) a *fully deterministic* greedy/explicit construction — the nibble is "semi" because each round is random but the *sequence* of rounds, the reweighting between rounds, and the stopping condition are all deterministically controlled based on the (concentrated, hence nearly-deterministic) state after the previous round. - This wiki's Erdős-problem applications (large prime gaps Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), Jacobsthal function Erdős #687 — estimate the Jacobsthal covering function Y(x), dense Sidon sets Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, $B_h$-sets Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, $R(3,k)$ asymptotics Erdős #165 — asymptotic formula for the Ramsey number R(3,k), $C_4$-free Ramsey Erdős #159 — polynomial improvement to R(C4,Kn) upper bound, probabilistic sparsification Erdős #74 — almost-bipartite graph of infinite chromatic number) are all documented, with the specific role the nibble plays in each, under Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings's ## Related section.

Technique

When it applies / the reusable recipe / why it works: identical to Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — see that page's ## Technique section in full, including the six-step recipe (cast as hypergraph matching/covering/colouring → verify near-regularity and low codegree → take one nibble → prove concentration for the leftover → iterate $\Theta(\log D)$ rounds → finish the residual via absorption if an exactly-perfect structure is needed) and the "portable recombination hooks" for deciding when this technique is a strong default candidate for a new open problem.

Related

- Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings — the canonical, fully-sourced page for this technique. Read that page for the precise statement, facts, technique recipe, and Erdős-problem applications; this page is a thin alias so that the slug concept/semi-random-nibble-method (as used by the literature and by cross-references elsewhere in this wiki) resolves to real content instead of a dead link. - Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), Erdős #687 — estimate the Jacobsthal covering function Y(x), Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf, Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Erdős #159 — polynomial improvement to R(C4,Kn) upper bound, Erdős #74 — almost-bipartite graph of infinite chromatic number — Erdős problems where this technique is load-bearing; see Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings for the specifics of each application. - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the classical concentration tool used in the original 1985 nibble proofs. - R-spread set families (ALWZ/Rao's central reduction device) — a structurally different, non-iterative modern alternative for the same broad class of existence questions. </content>