A linear programming perspective on the Frankl-Rödl-Pippenger theorem

For ℋ a hypergraph on vertex set V and t: ℋ → R⁺ , set a(t) = max{∑ {t(A):x, y ∈ A ∈ ℋ} :x, y ∈V, x ≠ y} . We give a simple proof, based on an argument of Pippenger and Spencer [19] of the following rather general statement. Theorem 1.5. Fix k and l. Let ℋ be a k-bounded hypergraph and t a fractional matching of ℋ. Let, furthermore, C₁ , . . . , C_i : ℋ → R⁺ , each satisfying ∑_A∈ℋ c²_i(A)t(A)<o((∑_A∈ℋ c_i(A)t(A))²). Then there is matching M of ℋ satisfying ∑_A∈ℋ c_i(A)∼c_i(ℋ) for i = 1 , . . . , l, limits taken as α(t)→0. This contains some previously announced results of the author which interpreted the theorem of the title as a statement about the relation between integer and linear programs and extended it in this vein.