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

For H a hypergraph on vertex set V and t : H → R + , set. α( t ) = max {Σ { t ( A ): x , y ϵ A ϵ H }: 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 H be a k‐bounded hypergraph and t a fractional matching of H. Let, furthermore, c 1 , …, c l : H → R + , each satisfying \documentclass{article}\pagestyle{empty}\begin{document}$ \sum_{A\in {\cal H}}\ c^2_i (A)t(A) \lt o\left(\left(\sum_{A\in {\cal H}}\ c_i(a)t(A)\right)^2\right) $\end{document} Then there is matching M of H satisfying \documentclass{article}\pagestyle{empty}\begin{document}$ \sum_{A\in {\cal M}} \ c_i(A) \sim c_i ({\cal H}) \kern4em \hbox{ for } i=1,\dots,l, $\end{document} 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. © 1996 John Wiley & Sons, Inc.