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

Research output: Contribution to journalArticlepeer-review

19 Scopus citations


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, C1 , . . . , Ci : ℋ → R+ , each satisfying ∑A∈ℋ c2i(A)t(A)<o((∑A∈ℋ ci(A)t(A))2). Then there is matching M of ℋ satisfying ∑A∈ℋ ci(A)∼ci(ℋ) 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.

Original languageEnglish (US)
Pages (from-to)149-157
Number of pages9
JournalRandom Structures and Algorithms
Issue number2
StatePublished - Mar 1996

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics


Dive into the research topics of 'A linear programming perspective on the Frankl-Rödl-Pippenger theorem'. Together they form a unique fingerprint.

Cite this