Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings

Statement

The Erdős–Hanani conjecture (1963), the problem the nibble was invented to solve. For a $k$-uniform hypergraph covering problem: let $M(n,k,l)$ be the minimum size of a family of $k$-element subsets of $\{1,\dots,n\}$ such that every $l$-element subset is contained in at least one member. Erdős and Hanani conjectured $$ \lim_{n\to\infty} \frac{M(n,k,l)}{\binom{n}{l}/\binom{k}{l}} = 1, $$ i.e. that the trivial counting lower bound is asymptotically tight — a near-perfect (asymptotically optimal) covering design exists. (en.wikipedia.org/wiki/Packing_in_a_hypergraph.) V. Rödl proved this asymptotically in 1985 ("On a packing and covering problem," *European J. Combin.* 6 (1985), 69–78) — this is the origin of "the Rödl nibble." The dual packing statement (find a near-perfect *matching*, i.e. pairwise-disjoint $k$-sets, in a near-regular low-codegree hypergraph) was proved the same year by Frankl and Rödl, "Near perfect coverings in graphs and hypergraphs," *European J. Combin.* 6 (1985), 317–326.

Modern quantified form (Kostochka–Rödl 1997, stated as Theorem 1.1 in Gould–Kelly arXiv:2511.11375). Suppose $1/D \ll 1/K, 1/k, \delta, \gamma < 1$. Let $H$ be a $(k+1)$-uniform, $(n,D,\varepsilon)$-regular hypergraph (every vertex has degree $D(1\pm\varepsilon)$) with 2-codegree $C_2(H)\le D_2\le D^{1-\gamma}$ (no pair of vertices lies in more than $D_2$ edges) and $\varepsilon \le K\sqrt{\log D / D}$. Then $H$ has a matching covering all but at most $$ n\,(D/D_2)^{-1/k+\delta} $$ vertices. This bound is essentially the optimal leftover achievable by *purely nibble-based* methods (heuristic: if the leftover survives with probability $p$, its expected degree is $Dp^k$, and $p=(D_2/D)^{1/k}$ is exactly where the leftover's typical degree drops to $D_2$ — the point at which the process can no longer usefully distinguish "structure" from "noise"). Vu (2000, "New bounds on nearly perfect matchings in hypergraphs: Higher codegrees do help," *Random Structures Algorithms* 17, 29–63) showed one can push further by tracking the decay of *higher* codegrees $D_3,D_4,\dots$ during the nibble, not just $D_2$, extracting a strictly larger matching when the codegree sequence permits it — refined further by Gould–Kelly (arXiv:2511.11375, Nov 2025), who show the nibble can "exhaust" the *entire* codegree sequence up to a natural information-theoretic bottleneck, and prove this is essentially optimal for any purely-nibble argument.

Pippenger–Spencer generalization to edge-colouring (1989). "Asymptotic behaviour of the chromatic index for hypergraphs," *J. Combin. Theory Ser. A* 51 (1989), 24–42: for every $k,\varepsilon>0$ there is $\delta>0$ such that if $H$ is a $k$-uniform, $D$-regular hypergraph with codegree at most $\delta D$, then the chromatic index $\chi'(H) \le (1+\varepsilon)D$ — i.e. $H$ can be (near-)properly edge-coloured with barely more than the trivial lower bound $D$ colours. The proof runs the nibble repeatedly, each round peeling off one *near-perfect matching* to use as a colour class, so that the accumulated colour classes leave a vanishing residual hypergraph. This was extended to *list*-edge-colouring by Kahn (1996) and sharpened by Molloy–Reed, "Near-optimal list colorings," *Random Structures Algorithms* 17 (2000), 376–402.

Facts

- Origin (1980–82) and naming. The semi-random method first appears in Ajtai, Komlós, Pintz, Spencer, Szemerédi, "Extremal uncrowded hypergraphs," *J. Combin. Theory Ser. A* 32 (1982), 321–335, and in Ajtai–Komlós–Szemerédi's 1981 dense infinite Sidon-set construction (used already in wiki/problems/39.md, giving $\gg(N\log N)^{1/3}$ via the nibble). Rödl's 1985 paper is where the technique became a general-purpose tool and acquired the "nibble" name (small random bites of the hypergraph taken repeatedly, as opposed to one large random gulp). - Frankl–Rödl 1985 vs. Rödl 1985. These are companion papers solving the two dual forms of the same problem: Rödl (covering, "On a packing and covering problem") proves the Erdős–Hanani conjecture; Frankl–Rödl ("Near perfect coverings...") proves the near-perfect *matching* form directly used by nearly all subsequent hypergraph-matching applications. - Pippenger–Spencer's "random greedy algorithm" equivalence. Pippenger and Spencer generalized Rödl's result and showed the packing achievable by the Rödl nibble is asymptotically the same as what a naive random-greedy edge-selection process achieves — the nibble is a way to *analyze* (via controlled rounds with concentration) what greedy random selection does "in one long uncontrolled pass," making the method both a construction and a proof technique for greedy processes. (en.wikipedia.org/wiki/Packing_in_a_hypergraph.) - Kim's $R(3,t)$ theorem (1995). J. H. Kim, "The Ramsey number $R(3,t)$ has order of magnitude $t^2/\log t$," *Random Structures Algorithms* 7(3) (1995), 173–207: builds a triangle-free graph on $n$ vertices with independence number $O(\sqrt{n\log n})$ via a semi-random ("nibble"/deletion) process, matching Shearer's 1983 entropy-based upper bound up to a constant and establishing $R(3,t)=\Theta(t^2/\log t)$. This is the canonical illustration of the nibble used for a *lower-bound existence* result (construct a pseudorandom object) rather than a packing/covering-design result. See Erdős #165 — asymptotic formula for the Ramsey number R(3,k), Erdős #159 — polynomial improvement to R(C4,Kn) upper bound. - Prime-gaps application (Ford–Green–Konyagin–Maynard–Tao, 2018). arXiv:1412.5029, "Long gaps between primes" (*J. Amer. Math. Soc.* 31(1), 2018): casts residue selection for a long prime-free interval as a hypergraph-covering problem (vertices = integers in the target window, edges = arithmetic progressions killed by each small prime's residue class) and generalizes Pippenger–Spencer's covering theorem to *non-uniform* edge sizes via per-round reweighting of the edge-selection probability — the key technical innovation over the classical (uniform-edge-size) nibble. This fully resolved the classical Erdős large-prime-gaps problem Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) and gives the current-best lower bound on the Jacobsthal function Erdős #687 — estimate the Jacobsthal covering function Y(x) (still open on the matching upper bound). - AKS/Ruzsa Sidon-set application (1981). Ajtai–Komlós–Szemerédi's paper introducing the semi-random method, applied there to build a dense infinite Sidon set $\gg(N\log N)^{1/3}$ — historically one of the first uses of the nibble outside design theory, predating even Rödl's own 1985 paper. See Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set, Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf. - A single nibble round, made precise (Gould–Kelly 2025 formalization, §6.1, arXiv:2511.11375). Fix a target "bite size" $p=\theta/\delta(H)$ for minimum degree $\delta(H)$. Independently include each edge $e\in E(H)$ in a random set $\mathbf X$ with probability $p$. Call $e$ *isolated* if $e\in\mathbf X$ and $e$ meets no other edge of $\mathbf X$; let $\mathbf M$ be the set of isolated edges — automatically a matching. Because a vertex's survival probability $p(v)=\Pr[v\notin V(\mathbf M)]$ varies slightly with $v$'s local structure, throw a further random "waste set" $\mathbf W$ (each $v$ included independently with probability $w(v)=(p^*-p(v))/(1-p(v))$, $p^*=\max_v p(v)$) so that **every vertex survives ($v\notin V(\mathbf M)\cup \mathbf W$) with exactly the same probability $1-p^*$** — this equalization is what lets the *next* round again be analyzed as a fresh near-regular hypergraph. Concentration for degree and codegree of the surviving hypergraph $H'$ is then obtained via the (asymmetric) Lovász Local Lemma or Talagrand/martingale-type inequalities, applied simultaneously to many tracked quantities across all vertices/pairs at once. - Why iterate rather than do it in one shot. A single random sparsification already gives a matching covering an $\Omega(1)$-fraction of vertices, but the *leftover* hypergraph is not simply "the same problem at smaller scale" — naive iteration compounds error. The technical content of the nibble is exactly the concentration machinery (originally: Chebyshev/variance + union bound over "bad" low-probability events; now typically Lovász Local Lemma or Talagrand's inequality) needed to show that degree drops roughly linearly in $p$ per round while codegree drops roughly quadratically, so the *ratio* $D/D_2$ shrinks favorably for $O(\log D)$ rounds before the process must stop (when degree and codegree become comparable, i.e. the leftover graph is too "clustered" to treat as pseudorandom). - Related but distinct modern black-box tools. The nibble constructs a *large* matching/colouring leaving a small, uncontrolled leftover; absorption method (iterative absorption, Glock–Kühn–Lo–Osthus and successors, e.g. arXiv:2510.19978 "Refined Absorption") is typically combined with the nibble to *finish the job*: run a nibble to cover all but $o(n)$ vertices, then use a separately-constructed small "absorbing" substructure to swallow the leftover and complete a genuinely perfect matching/design/decomposition. Most modern existence-of-designs results (Keevash 2014; Glock–Kühn–Lo–Osthus) are nibble+absorption hybrids, not nibble alone.

Technique

When it applies. Any time you want to prove that a large, "spread-out"/almost-regular combinatorial structure (a hypergraph, a set of colour classes, a Latin-square transversal system, a family of arithmetic progressions/residue classes) admits an almost-perfect sub-object — a near-perfect matching, near-optimal edge-colouring, near-complete packing/covering design, a dense pseudorandom subset avoiding some structure — under a low-codegree / bounded-clustering hypothesis (no small set of vertices is contained in too many edges relative to the overall degree). It is the standard tool whenever the naive random-greedy or first-moment argument gets "stuck" because dependencies between potential choices (shared vertices/pairs) prevent a clean one-shot probabilistic argument, but those dependencies are *weak enough* (codegree $\ll$ degree) that a controlled, iterated random process can out-run them.

The reusable recipe

1. Cast the target as a hypergraph matching/covering/colouring problem. Vertices = "resources to be used up," edges = "candidate structures" (a potential Steiner block, an edge-colour class, an arithmetic-progression residue choice, a potential sunflower/design piece). This reformulation step is itself often the hard creative part (as in FGKMT's prime-gaps hypergraph, Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)). 2. Verify near-regularity and low codegree. The hypergraph should be $(n,D,\varepsilon)$-regular (degrees within $D(1\pm\varepsilon)$) with codegree $D_2 \ll D$ (ideally $D_2 \le D^{1-\gamma}$ for constant $\gamma>0$) — this is the structural hypothesis that makes the nibble applicable at all; if codegree and degree are comparable, the process stalls immediately and other tools (absorption from scratch, algebraic constructions) are needed instead. 3. Take one nibble. Randomly select a sparse sub-collection of edges (probability $p\approx 1/\delta(H)$ per edge, or equivalently expected sub-collection size proportional to $n/D$), keep only the *isolated* ones (forming a genuine matching), optionally add a "waste set" of vertices to equalize survival probabilities across vertices (Gould–Kelly's formalization; classical treatments often absorb this into the concentration step directly). 4. Prove concentration for the leftover hypergraph. Show that, with high probability, the surviving vertex set again induces a near-regular, low-codegree hypergraph — with degree reduced by roughly a $(1-p)^k$ factor and codegree reduced *faster* (roughly $(1-p)^{2k}$-ish, the key asymmetry making iteration worthwhile). Historically via second-moment/Chebyshev arguments (original Rödl 1985, Frankl–Rödl 1985); modern treatments use the Lovász Local Lemma or Talagrand-type/martingale concentration inequalities to control many tracked quantities (degree, several orders of codegree, auxiliary weight functions for "pseudorandomness" against a target family) simultaneously in one round. 5. Iterate for $\Theta(\log D)$ rounds (recent refinements: "chomp" together $\sim\log^3 D$ nibbles at once, Gould–Kelly arXiv:2511.11375 §7), accumulating the matching/colour-classes, until the ratio $D/D_2$ collapses and the leftover hypergraph is too small/clustered to usefully nibble further. This leaves an explicit, small (typically $n^{1-\Omega(1)}$ or $n\cdot(D/D_2)^{-1/k+\delta}$) uncovered residual. 6. **Finish the residual, if a *perfect* (not just near-perfect) structure is required. Options: (a) accept the near-perfect result if that suffices for the application (most Ramsey/Sidon-set lower-bound uses only need near-perfect); (b) combine with the absorption method** — construct in advance a small "absorber" gadget that can incorporate an arbitrary small leftover set into a valid completion (this is the dominant modern strategy for exact design/decomposition existence results); (c) apply a second, differently-tuned nibble targeting the specific residual structure.

Why it works (the core mechanism). The nibble exploits an asymmetry in how randomness degrades structure: taking a random $p$-fraction of edges (and removing everything touched) reduces a vertex's *degree* by a factor $\approx(1-p)^{k}$ (linear-ish in $p$ for small $p$), but reduces a *pair's* codegree by a much steeper factor $\approx(1-p)^{2k}$ or worse, because a pair surviving requires *two* separate vertex-survival events to align. Concretely, if the leftover graph after removing mass $1-q$ resembles an independently-thinned copy of the original with retention probability $q$, then a vertex's degree in the leftover is $\approx Dq^k$ while its codegree is $\approx D_2 q^{2k-2}$ or similar — the *ratio* $D_2/D$ (which measures "how far from perfectly regular/pseudorandom" the hypergraph is) shrinks with each round. This means you can profitably repeat the random-sparsify-and-take-the-matching step many times (not just once), each time re-establishing (via concentration) that the leftover is again well-behaved enough to nibble further, until the shrinking ratio $D/D_2$ forces a stop — at which point what remains is provably tiny. The concentration step (originally Chebyshev/second moment, now typically Lovász Local Lemma) is what upgrades "true on average" into "true with high probability simultaneously for every vertex and every tracked codegree," which is essential because the *next* round's validity depends on *all* of these holding at once, not just in expectation.

Portable recombination hooks. - If a target Erdős problem is of the shape "does there exist a covering/packing/colouring of a hypergraph-like structure that is asymptotically as efficient as the trivial counting bound," check whether the natural incidence structure is near-regular with codegree $\ll$ degree — if so, the nibble is a strong default candidate, and the main creative work is (a) the hypergraph reformulation (step 1) and (b) whatever nonstandard concentration/reweighting is needed for non-uniform or highly structured edge sets (as in FGKMT's reweighted nibble for prime gaps, Erdős #4 — unbounded large gaps between primes (Rankin's constant removed), Erdős #687 — estimate the Jacobsthal covering function Y(x)). - If the near-perfect result from a pure nibble is not quite good enough (an $n^{1-\Omega(1)}$ leftover matters), check the recent codegree-sequence-exhausting refinements (Vu 2000; Gould–Kelly 2025, arXiv:2511.11375) before assuming the nibble itself is out of gas — these squeeze meaningfully more out of the same basic machinery by tracking more of the codegree sequence. - If an *exactly* perfect structure (not just near-perfect) is required, pair the nibble with the absorption method rather than trying to push the nibble's leftover to literally zero (which pure nibble methods provably cannot do, per Gould–Kelly's "optimal usage of pure nibble methodology" discussion).

Related

- Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — Erdős's large-prime-gaps problem; PROVED by Ford–Green–Konyagin–Maynard–Tao (arXiv:1412.5029) via a reweighted Pippenger–Spencer-style Rödl-nibble hypergraph-covering construction handling non-uniform edge sizes. - Erdős #687 — estimate the Jacobsthal covering function Y(x) — the sibling Jacobsthal-function problem (still open on the upper-bound side); the same FGKMT nibble machinery gives the current-best *lower* bound, but the technique is constructive/existence-proving and cannot by itself supply the needed impossibility (upper-bound) result. - Erdős #39 — density $N^{1/2-\\epsilon}$ infinite Sidon set — dense infinite Sidon sets; Ajtai–Komlós–Szemerédi's 1981 paper (historically the first use of the semi-random method, predating Rödl's own 1985 paper) gives $\gg(N\log N)^{1/3}$, since superseded by Ruzsa's non-nibble discrete-log-based construction. - Erdős #41 — $B_3$ (distinct-triple-sum) set density liminf — closely related $B_h$-set density question; nibble-based constructions are the historical state of the art before more recent explicit algebraic constructions. - Erdős #165 — asymptotic formula for the Ramsey number R(3,k) — $R(3,k)$ asymptotics; Kim's 1995 nibble-based lower bound $\Omega(k^2/\log k)$ was the long-standing record (matching Shearer's upper bound up to constant) until 2025 pseudorandom-construction improvements (Campos–Jenssen–Michelen–Sahasrabudhe; Hefty–Horn–King–Pfender) surpassed it with nibble-free methods — a useful cautionary data point that the nibble, while historically foundational, is not always the asymptotically optimal tool even in its own signature application. - Erdős #159 — polynomial improvement to R(C4,Kn) upper bound — the $C_4$-free analogue of the $R(3,k)$ problem; Kim's nibble template is the natural (so far unsuccessful) candidate for the matching upper-bound direction. - Erdős #74 — almost-bipartite graph of infinite chromatic number — probabilistic sparsification bound; flagged as a candidate for a genuine sub-linear improvement via post-1985 nibble methods (the original 1982 construction predates Rödl's paper). - Second moment method / Paley–Zygmund inequality — variance-based random-structure existence proofs — the classical concentration tool used in the original 1985 Rödl/Frankl–Rödl nibble proofs, later largely superseded by the Lovász Local Lemma and Talagrand-type inequalities in modern nibble formalizations for handling many simultaneously-tracked quantities per round. - R-spread set families (ALWZ/Rao's central reduction device) — a structurally different (non-iterative) modern reduction device for "large family ⇒ contains substructure" problems; worth contrasting with the nibble's iterative-and-shrinking approach to the same broad class of existence questions.