The Setting
Take an -uniform hypergraph on a finite set in which every vertex lies in close to edges and any two vertices lie together in far fewer than edges. The question is whether some matching covers all but a fraction of once is large and the departures from regularity and the codegrees are small compared with : 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 be an integer. An -uniform hypergraph on a finite set is a finite family of -element subsets of , its edges, indexed by a finite set , repetitions allowed. The elements of are the vertices of .
The set of edges incident to a vertex is the set of indices with .✦ The degree of is the number of edges incident to it, and the codegree of two vertices is the number of edges incident to both: (1)
A matching of is a set of indices whose edges are pairwise disjoint: for distinct .
The Random Slot Hypergraph
Let be a finite field, a finite vector space over , and a family of linear functionals indexed by a finite set . The fiber of over is the set of vectors with ✦. The average of a real function on a finite set is (2)✦
A slot is a pair , and the slot support of a vector is the set of slots , .✦ Given sets of hit values, one for each , the slot vertices are the hit slots✦ and the slot edges are the vectors all of whose values are hit: (3)✦ The slot hypergraph of is the hypergraph on whose edges are the slot supports of the vectors ; a matching of it is a set of slot edges with pairwise disjoint slot supports.
The slot density of a slot is the fraction of the fiber whose values at the other functionals are all hit: (4)✦
A random slot hypergraph is given by a finite nonempty set of outcomes, averaged uniformly, and for each outcome and each a set of hit values; , and are the slot vertices, the slot edges and the slot densities of the outcome .
The Claim
Theorem 1. Let be an integer and let and be real numbers.
(a) There are and with the following property. Let be an -uniform hypergraph on a finite set , and let and be real numbers with , , and . If for every vertex and for every two distinct vertices , with the degrees and codegrees (1), then has a matching with (5)✦
(b) There are and with the following property. Let be an -uniform hypergraph on a finite set , let be a set of atypical vertices, and let and be real numbers with , , , and . If for every vertex and for every two distinct vertices , then has a matching with (6)✦
(c) Suppose moreover that , and let be a finite set of indices. There are and with the following property. Let be a finite field, a finite vector space over , and linear functionals on , each mapping onto and each pair with mapping onto . Let a random slot hypergraph be given on a finite nonempty set of outcomes, let , , and be real numbers, and put and . Suppose that every outcome has exactly slot vertices, that the slot densities (4) satisfy for every , with the averages (2), and that , , , , and . Then some outcome has a matching of its slot hypergraph with (7)✦
In the paper, the result reads, with standing for the paper’s : for every and there is such that every -uniform hypergraph with for every vertex and codegrees for every two distinct vertices can be edge-colored with at most matchings.
What Is Checked
The claim is stated over -uniform hypergraphs given as finite families of -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.