Pippenger–Spencer hypergraph covering theorem (and the FGKMT generalization)

Statement

Classical Pippenger–Spencer theorem (1989; restated verbatim from the Visser essay's Theorem 10, itself quoting [Pippenger, Spencer 1989, p.25]):

For every $k\ge 2$ and $\delta>0$, there exists a positive integer $N$ and $\delta'>0$ such that: let $(V,E)$ be a hypergraph with $|V|>N$, maximum degree $D:=\max_{v\in V}d(v)$, satisfying

- ($k$-uniform) every edge has exactly $k$ vertices; - (near-regular) every $v\in V$ has $d(v)\ge(1-\delta')D$; - (small codegree) every distinct $v,w\in V$ has $\mathrm{codeg}(v,w)\le \delta' D$ (number of edges containing both $v$ and $w$).

Then both of the following hold:

1. (Packing / chromatic index) $E$ can be partitioned into packings (matchings) $E_1,\dots,E_r$ with $r\le(1+\delta)D$ — i.e. the chromatic index $\chi(G)\le(1+\delta)D$. 2. (Covering) $E$ can be partitioned into coverings $E_1,\dots,E_r$ (each $E_i$ touches every $v\in V$ at least once) with $r\ge(1-\delta)D$.

An immediate corollary: there exists a single covering $C\subseteq E$ of size $|C|\le \frac{1}{1-\delta}\cdot\frac{|V|}{k}$ — essentially matching the trivial lower bound $|V|/k$ (any $k$-uniform covering needs $\ge|V|/k$ edges), i.e. an asymptotically optimal covering. Equivalently, the matching form: any such $(V,E)$ has a matching covering all but at most $\varepsilon|V|$ vertices for $\varepsilon\to0$ as $\delta,\delta'\to0$ — this is the "nearly perfect matching" formulation most often cited. The result strengthens and generalizes earlier existence-only results of Rödl (1985) and Frankl–Rödl (1985) on near-perfect packings/coverings, and in particular resolves the asymptotic chromatic index of Steiner triple systems.

FGKMT generalized covering theorem (Ford, Green, Konyagin, Maynard, Tao, 2018, JAMS 31(1):65–105, arXiv:1412.5029; restated verbatim from the Visser essay's Theorem 11, quoting [FGKMT18, p.12]) — the key upgrade is that edges no longer need constant size, at the cost of working with a fully probabilistic/weighted formulation:

There is a constant $C_0\ge1$ such that: let $D,r,A\ge1$, $0<\kappa\le1$, $m\ge0$ an integer, and $\delta>0$ satisfying $$\delta \le \left(\frac{\kappa A}{C_0 e A D}\right)^{10^{m+2}}.$$ Let $V$ be a finite vertex set and $I_1,\dots,I_m$ disjoint finite index sets; for $j=1,\dots,m$ and $i\in I_j$, let $e_i$ be a random finite subset of $V$. Assume:

- (A1, bounded edge size) $|e|\le r$ for all $e$ in the range of every $e_i$; - (A2, sparse sieve step) $\mathbb P(v\in e_i)\le \delta/|I_j|^{1/2}$ for all $j,i\in I_j,v\in V$; - (A3, small codegree) $\sum_{i\in I_j}\mathbb P(v_1,v_2\in e_i)\le\delta$ for all distinct $v_1,v_2\in V$; - (A4, bounded normalized degree) defining $d_{I_j}(v):=\sum_{i\in I_j}\mathbb P(v\in e_i)$ and recursively $P_0(v):=1$, $P_{j+1}(v):=P_j(v)\exp(-d_{I_{j+1}}(v)/P_j(v))$, require $d_{I_j}(v)\le D\,P_{j-1}(v)$ and $P_j(v)\ge\kappa$ for all $j,v$.

Then there exist random variables $e_i'$ (each either $\varnothing$ or a value the original $e_i$ attains with positive probability) such that for any $0\le J\le m$ and any $e\subseteq V$ with $|e|\le A-2rJ$: $$\mathbb P\Big(e\subseteq V\setminus\bigcup_{j\le J}\bigcup_{i\in I_j}e_i'\Big) = \big(1+O(\delta^{1/10^{J+1}})\big)\,P_J(e),\qquad P_j(e):=\prod_{v\in e}P_j(v).$$

In words: it lets you run the nibble in stages $I_1,\dots,I_m$ over edges of varying, only size-bounded cardinality, and still control — to high precision, via the deterministic "survival probability" recursion $P_j(v)$ — the probability that any small target set $e$ survives uncovered after $J$ stages. A purely combinatorial special case (Corollary 2 of the 2015 arXiv draft, arXiv:1412.5029v1 p.13) recovers Theorem 10 exactly when edge sizes are constant.

Facts

- Both are proved by the Rödl nibble (semi-random method): repeatedly (1) sample a *small* random sub-collection of edges (probability $\sim\varepsilon/D$ per edge) so that with high probability the sampled edges are pairwise disjoint, (2) delete every edge that intersects a sampled edge, (3) repeat on the shrunk hypergraph. Naive one-shot random sampling would need $\sim(-\log\varepsilon)|V|/k$ edges to cover $(1-\varepsilon)|V|$ vertices (suboptimal by a log factor); the staged nibble gets down to $\sim(1+\varepsilon)|V|/k$, i.e. asymptotically optimal. Rödl introduced this in response to the Erdős–Hanani conjecture on the size of near-optimal coverings/packings, which the theorem was originally built to resolve. - The classical theorem cannot be applied directly to variable-edge-size problems: if edges have different sizes, larger edges are hit (and hence eliminated) by the nibble at a rate proportional to their size, so they get disproportionately killed relative to how much "coverage value" they carry — exactly backwards from what an efficient covering needs (large edges are the ones you *want* to keep using). FGKMT's fix, described by the authors as their "main new ingredient," is to iteratively reweight the sampling probability distribution at each nibble stage to compensate — giving larger edges systematically more weight so their elimination rate matches their coverage value (terrytao.wordpress.com/2014/12/16/long-gaps-between-primes). - Chain of generalization: Rödl (1985, packing/covering existence) → Frankl–Rödl (1985, "Near perfect coverings in graphs and hypergraphs") → Pippenger–Spencer (1989, sharpened to near-optimal chromatic index, i.e. simultaneous packing *and* covering, Theorem 10 above) → Kahn (1996, "A linear programming perspective on the Frankl–Rödl–Pippenger theorem," relaxes some hypotheses via an LP-duality argument, Random Structures & Algorithms 8(2):149–157) → Ford–Green–Konyagin–Maynard–Tao (2018, variable edge size via reweighted nibble, Theorem 11 above). Kahn's 1996 relaxation was investigated by FGKMT as an alternative but found "not applicable in a format which we can use" for the prime-gaps application (Visser essay, p.26) — they built their own generalization instead. - Concrete worked application (Corollary 12 of the Visser essay, quoting FGKMT18 p.13): to build an efficient covering of an interval by residue classes $a_p\bmod p$ over primes $p$ in a range $P$, against a target set $Q$ of size up to $x^{100}$, with edge sizes up to $\frac{\log x\log_3 x}{(\log_2 x)^2}$, sparse sieve probability $\le x^{-3/5}$, and codegree sum $\le x^{-1/20}$ — the theorem is applied with parameters $D:=2\log5$, $r:=\frac{\log x\log_3 x}{(\log_2x)^2}$, $A:=2rm+2$, $\kappa:=\frac{1}{2\log_2x}$, $\delta:=x^{-1/20}$, over $m\le \frac{\log_3 x}{\log 5}$ stages (index sets $I_j$ built by partitioning primes according to i.i.d. uniform "arrival times" $t_p\in[0,1]$ split into $m$ geometrically-shrinking intervals) — yielding a covering that leaves only a $5^{-m}$-fraction of $Q$ uncovered. This directly powers the current-best lower bound on large prime gaps, $g_n\gg\frac{\log n\log\log n\log\log\log\log n}{\log\log\log n}$, resolving Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) and giving the best known lower bound for the Jacobsthal-function problem Erdős #687 — estimate the Jacobsthal covering function Y(x). - This theorem answers a "how efficiently can I cover/pack a hypergraph" question, not a "does a perfect matching/covering exist" question — it is inherently an *asymptotic, near-optimal* statement (leaves an $\varepsilon$-fraction uncovered / an $o(D)$-size excess), not an exact combinatorial-design existence theorem (contrast Keevash's exact existence-of-designs result, arxiv.org/pdf/1401.3665, which also uses nibble-style absorption but targets *exact* perfect designs rather than near-perfect ones).

Technique

WHY it works (the mechanism). A single random edge-selection round, done carefully at *low enough density* ($\Pr(v\in e_i)\lesssim \varepsilon/D$), makes edge-overlaps a lower-order effect: the expected number of vertices "wasted" by overlapping edges within one nibble round is $O(\varepsilon^2)$-small compared to the $O(\varepsilon)$ vertices newly covered, so each nibble round covers close to its "fair share" of remaining vertices with controlled loss. Iterating $\Theta(\log(1/\varepsilon))$ rounds, each shrinking the uncovered set geometrically (by a constant factor per round, since degrees stay high on the un-eliminated vertices thanks to the near-regularity + small-codegree hypotheses, which prevent any single vertex's neighborhood from collapsing disproportionately), drives the uncovered fraction down to $\varepsilon$ while using close to the information-theoretically optimal number of edges. Codegree control is what prevents pairs of vertices from being "double-covered" wastefully, which is what makes the bound tight rather than merely existent. The FGKMT reweighting is the same mechanism with an extra degree of freedom: the sampling *weight* per edge is allowed to depend on its size and stage, and the martingale-like recursion $P_j(v)=P_{j-1}(v)\exp(-d_{I_j}(v)/P_{j-1}(v))$ tracks — deterministically, in the large-$D$ limit — the probability a given vertex survives uncovered, letting the reweighting exactly compensate for large edges' higher elimination rate.

HOW to use it to prove things (recombination steps)

1. Recast the target combinatorial existence problem as a hypergraph covering/matching/edge-coloring problem. Vertices = the objects you need to hit/cover/color; edges = the "moves" available (e.g. one residue class mod one prime; one color class; one block of a design). This is the universal first step — see Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)'s use (vertices = integers in a target window, edges = arithmetic progressions killed by a prime's residue choice) and Erdős #687 — estimate the Jacobsthal covering function Y(x)'s identical reduction (Jacobsthal function). 2. Check (or engineer) the three/four structural hypotheses: bounded/controlled edge size, approximate regularity of degrees (every vertex is covered by "enough" edges, roughly equally), and small codegree (no pair of vertices is jointly over-covered). If edges are naturally uniform-size, apply the classical Theorem 10 directly. If edge sizes vary, you need the FGKMT machinery (Theorem 11) — and specifically its reweighting to avoid the large-edges-die-first pathology. 3. Choose the free parameters ($D$ = the "typical" per-stage degree, $r$ = edge-size bound, $\kappa$ = survival-probability floor, $m$ = number of nibble stages, $\delta$ = smallness parameter satisfying the tower-exponential bound in $m$) to match your problem's scale — as in Corollary 12's worked example above. 4. Run/cite the theorem to get a near-optimal covering/matching/packing with quantified excess (an $\varepsilon|V|$-size uncovered remainder, or an explicit $(1+O(\delta^{1/10^{J+1}}))$-type multiplicative error). 5. Convert the combinatorial covering back into the original problem's answer — e.g. "this covering system certifies every integer in $(n,n+y]$ is composite, hence $p_{n+1}-p_n>y$" (Erdős #4 — unbounded large gaps between primes (Rankin's constant removed)'s exact next step, documented in Erdős–Rankin construction (covering-congruences translation for large prime gaps)).

WHEN it applies: any existence problem that reduces to "cover/pack/edge-color a hypergraph whose edges have bounded size, roughly-uniform per-vertex degree, and small pairwise codegree" — this is an extremely common shape for probabilistic-combinatorics existence proofs (Steiner systems, Latin square transversals, list-edge-coloring, covering designs, and — via the Erdős–Rankin translation — prime-gap and covering-congruence problems). **When it does *not* apply directly**: (a) it is inherently asymptotic/near-optimal — for *exact* perfect coverings/designs, a stronger "absorption method" is needed on top (see e.g. Keevash's existence-of-designs work, arxiv.org/pdf/1401.3665, or the iterative-absorption / "conflict-free hypergraph matchings" line, e.g. Glock et al., JLMS 2024, londmathsoc.onlinelibrary.wiley.com/doi/abs/10.1112/jlms.12899); (b) the classical form needs genuinely near-uniform edge size — non-uniform-size problems need the heavier FGKMT probabilistic machinery, or Kahn's LP-relaxation variant, and even then only if the FGKMT hypotheses (A1–A4) can be verified for your specific random-edge construction; (c) it gives *existence*, not an explicit/efficient construction — the nibble is a probabilistic existence argument, not (without further derandomization work) an algorithm.

Related

- Erdős–Rankin construction (covering-congruences translation for large prime gaps) — the number-theoretic *application* this concept is imported into: translating "long prime-free interval" into "hypergraph covering exists," where this theorem supplies the covering. - Erdős #4 — unbounded large gaps between primes (Rankin's constant removed) — large prime gaps (Rankin's constant): SOLVED, using exactly the FGKMT generalized covering theorem (Theorem 11 above) as the "main new ingredient" over the classical Pippenger–Spencer form. - Erdős #687 — estimate the Jacobsthal covering function Y(x) — Jacobsthal function $Y(x)$: OPEN upper bound; best known lower bound comes from the identical covering-theorem machinery. - Concept referenced but not yet its own page: "Rödl nibble / semi-random method" (the proof engine underlying both Theorem 10 and Theorem 11 — already forward-linked as `Rödl nibble / semi-random greedy method — iterated small-random-selection for near-perfect hypergraph matchings, packings, and colourings / Semi-random method (Rödl nibble) — alias page; canonical content at concept/rodl-nibble` from problems/4.md and problems/687.md in this wiki) and "absorption method" (the complementary technique needed to upgrade near-perfect coverings/matchings from this theorem into *exact* perfect ones, e.g. in Keevash's design-existence theorem, arxiv.org/pdf/1401.3665) — both flagged here as natural next concept pages.