A linear programming perspective on the Frankl?R�dl?Pippenger theorem

Abstract

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, c1, …, cl: 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.