OctoInformBeta

OpenAI preprint, September 2026 · §3. Packing signed intervals

Theorem 3.2: Degrees near a large DD and small codegrees give a matching missing at most η|U|\eta|U| vertices, with variants after pruning and for slot hypergraphs

Almost perfect matchings in nearly regular hypergraphs with small codegrees.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take an rr-uniform hypergraph on a finite set UU in which every vertex lies in close to DD edges and any two vertices lie together in far fewer than DD edges. The question is whether some matching covers all but a fraction η\eta of UU once DD is large and the departures from regularity and the codegrees are small compared with DD: the regime of nearly perfect matchings and the Rödl nibble.

In the section on packing signed intervals of the paper on asymptotically minimal maxima of real Littlewood polynomials, the proof of Lemma 3.1 applies such a matching theorem to a random hypergraph whose vertices are slots, pairs of an index and a field element, and whose edges come from linear functionals on a vector space over a finite field. The library states the matching theorem for a single hypergraph, for a single hypergraph with a set of atypical vertices set aside, and for the random slot hypergraph.

Hypergraphs and Matchings

Let r≥1r\ge 1 be an integer. An rr-uniform hypergraph ℋ\mathcal H on a finite set UU is a finite family (Ai)i∈S(A_i)_{i\in S} of rr-element subsets of UU, its edges, indexed by a finite set SS, repetitions allowed. The elements of UU are the vertices of ℋ\mathcal H.

The set S(v)S(v) of edges incident to a vertex v∈Uv\in U is the set of indices i∈Si\in S with v∈Aiv\in A_i.✦ The degree d(v)d(v) of vv is the number of edges incident to it, and the codegree d(v,w)d(v,w) of two vertices v,w∈Uv,w\in U is the number of edges incident to both: d(v)=|S(v)|,d(v,w)=|S(v)∩S(w)|.d(v)=|S(v)|,\qquad d(v,w)=|S(v)\cap S(w)|.(1)

A matching of ℋ\mathcal H is a set M⊆SM\subseteq S of indices whose edges are pairwise disjoint: Ai∩Aj=∅A_i\cap A_j=\emptyset for distinct i,j∈Mi,j\in M.

The Random Slot Hypergraph

Let 𝔽\mathbb F be a finite field, VV a finite vector space over 𝔽\mathbb F, and (gi)i∈I(g_i)_{i\in I} a family of linear functionals gi:V→𝔽g_i\colon V\to\mathbb F indexed by a finite set II. The fiber of gig_i over s∈𝔽s\in\mathbb F is the set gi−1(s)g_i^{-1}(s) of vectors y∈Vy\in V with gi(y)=sg_i(y)=s✦. The average of a real function ff on a finite set XX is 𝔼x∈Xf(x)=1|X|∑x∈Xf(x).\mathbb E_{x\in X}\,f(x)=\frac{1}{|X|}\sum_{x\in X}f(x).(2)✦

A slot is a pair (i,s)∈I×𝔽(i,s)\in I\times\mathbb F, and the slot support supp⁡(y)\operatorname{supp}(y) of a vector y∈Vy\in V is the set of slots (i,gi(y))(i,g_i(y)), i∈Ii\in I.✦ Given sets Hi⊆𝔽H_i\subseteq\mathbb F of hit values, one for each i∈Ii\in I, the slot vertices are the hit slots✦ and the slot edges are the vectors all of whose values are hit: UH={(i,s)∈I×𝔽:s∈Hi},EH={y∈V:gi(y)∈Hifor everyi∈I}.U_H=\{(i,s)\in I\times\mathbb F: s\in H_i\},\qquad E_H=\{y\in V: g_i(y)\in H_i\ \text{for every}\ i\in I\}.(3)✦ The slot hypergraph of (Hi)i∈I(H_i)_{i\in I} is the hypergraph on UHU_H whose edges are the slot supports of the vectors y∈EHy\in E_H; a matching of it is a set M⊆EHM\subseteq E_H of slot edges with pairwise disjoint slot supports.

The slot density ρi(s)\rho_i(s) of a slot (i,s)(i,s) is the fraction of the fiber gi−1(s)g_i^{-1}(s) whose values at the other functionals are all hit: ρi(s)=𝔼y∈gi−1(s)∏j≠i𝟏[gj(y)∈Hj].\rho_i(s)=\mathbb E_{y\in g_i^{-1}(s)}\prod_{j\ne i}\mathbf 1\bigl[g_j(y)\in H_j\bigr].(4)✦

A random slot hypergraph is given by a finite nonempty set Ω\Omega of outcomes, averaged uniformly, and for each outcome ω\omega and each i∈Ii\in I a set Hi(ω)⊆𝔽H_i(\omega)\subseteq\mathbb F of hit values; U(ω)U(\omega), E(ω)E(\omega) and ρiω\rho_i^\omega are the slot vertices, the slot edges and the slot densities of the outcome ω\omega.

The Claim

Theorem 1. Let r≥1r\ge 1 be an integer and let κ≥0\kappa\ge 0 and η>0\eta>0 be real numbers.

(a) There are β>0\beta>0 and D0>0D_0>0 with the following property. Let ℋ\mathcal H be an rr-uniform hypergraph on a finite set UU, and let DD and CC be real numbers with D≥D0D\ge D_0, |U|≥D0|U|\ge D_0, 0≤C≤βD0\le C\le\beta D and |U|C≤κD|U|\,C\le\kappa D. If |d(v)−D|≤βD|d(v)-D|\le\beta D for every vertex v∈Uv\in U and d(v,w)≤Cd(v,w)\le C for every two distinct vertices v,w∈Uv,w\in U, with the degrees and codegrees (1), then ℋ\mathcal H has a matching MM with r|M|≥(1−η)|U|.r\,|M|\ge(1-\eta)\,|U|.(5)✦

(b) There are β>0\beta>0 and D0>0D_0>0 with the following property. Let ℋ\mathcal H be an rr-uniform hypergraph on a finite set UU, let B⊆UB\subseteq U be a set of atypical vertices, and let DD and CC be real numbers with D≥D0D\ge D_0, |U\B|≥D0|U\setminus B|\ge D_0, 0≤C≤βD0\le C\le\beta D, |U|C≤κD|U|\,C\le\kappa D and |B|C≤βD/2|B|\,C\le\beta D/2. If |d(v)−D|≤βD/2|d(v)-D|\le\beta D/2 for every vertex v∈U\Bv\in U\setminus B and d(v,w)≤Cd(v,w)\le C for every two distinct vertices v,w∈Uv,w\in U, then ℋ\mathcal H has a matching MM with r|M|≥(1−η)|U\B|.r\,|M|\ge(1-\eta)\,|U\setminus B|.(6)✦

(c) Suppose moreover that η≤1\eta\le 1, and let II be a finite set of rr indices. There are β>0\beta>0 and D0>0D_0>0 with the following property. Let 𝔽\mathbb F be a finite field, VV a finite vector space over 𝔽\mathbb F, and (gi)i∈I(g_i)_{i\in I} linear functionals on VV, each mapping VV onto 𝔽\mathbb F and each pair (gi,gj)(g_i,g_j) with i≠ji\ne j mapping VV onto 𝔽2\mathbb F^2. Let a random slot hypergraph be given on a finite nonempty set Ω\Omega of outcomes, let p>0p>0, aa, b≥0b\ge 0 and nn be real numbers, and put D=p|V|/|𝔽|D=p\,|V|/|\mathbb F| and C=|V|/|𝔽|2C=|V|/|\mathbb F|^2. Suppose that every outcome has exactly nn slot vertices, that the slot densities (4) satisfy 𝔼ω∈Ω𝔼s∈𝔽(ρiω(s)−p)2≤a\mathbb E_{\omega\in\Omega}\,\mathbb E_{s\in\mathbb F}\,(\rho_i^\omega(s)-p)^2\le a for every i∈Ii\in I, with the averages (2), and that r|𝔽|a/(βp/2)2≤br\,|\mathbb F|\,a/(\beta p/2)^2\le b, D≥D0D\ge D_0, n−b≥D0n-b\ge D_0, C≤βDC\le\beta D, nC≤κDnC\le\kappa D and bC≤βD/2bC\le\beta D/2. Then some outcome ω\omega has a matching MM of its slot hypergraph with r|M|≥(1−η)(n−b).r\,|M|\ge(1-\eta)(n-b).(7)✦

In the paper, the result reads, with DD standing for the paper’s tt: for every r≥2r\ge 2 and γ>0\gamma>0 there is β>0\beta>0 such that every rr-uniform hypergraph with (1−β)D<d(v)<(1+β)D(1-\beta)D<d(v)<(1+\beta)D for every vertex vv and codegrees d(u,v)<βDd(u,v)<\beta D for every two distinct vertices u,vu,v can be edge-colored with at most (1+γ)D(1+\gamma)D matchings.

What Is Checked

The claim is stated over rr-uniform hypergraphs given as finite families of rr-element subsets of a finite set, with degrees and codegrees counted through the sets of incident edges and matchings as sets of pairwise disjoint edges, and over the slot hypergraphs of a family of linear functionals on a finite vector space over a finite field, with their slot vertices, slot edges, slot supports and slot densities, the last being averages over the fibers of the functionals.