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

✍ Scribed by Jeff Kahn

• Publisher: John Wiley and Sons
• Year: 1996
• Tongue: English
• Weight: 394 KB
• Volume: 8
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/(sici)1098-2418(199603)8:2<149::aid-rsa5>3.0.co;2-y

✦ Synopsis

For X a hypergraph on vertex set V and t : X+ R+, set

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 1. Let X be a k-bounded hypergraph and t a fractional matching of X. Let, furthermore, c , , . . . , c, : X + R + , each satisfying Then there is matching 1 of X satisfying f o r i = I , . .

. ,I, A E R limits taken as a(t)+O.

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. @