Fractional v. Integral Covers in Hypergraphs of Bounded Edge Size
✍ Scribed by Jeff Kahn; P.Mark Kayll
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 470 KB
- Volume
- 78
- Category
- Article
- ISSN
- 0097-3165
No coin nor oath required. For personal study only.
✦ Synopsis
In the early 1980's, V. Ro dl proved the Erdo s Hanani Conjecture, sparking a remarkable sequence of developments in the theory of packing and covering in hypergraphs of bounded edge size. Generalizations were given by P. Frankl and Ro dl, by N. Pippenger, and by others. In each case, an appropriate semi-random method was used to ``construct'' the desired optimal object (covering, matching, colouring) in several random stages, followed by a greedy stage. The current work, which further generalizes some of the above results, is again probabilistic, and uses, in addition to earlier ideas, connections with so-called hard-core distributions on the set of matchings of a graph. For fixed k 2, H a k-bounded hypergraph, and t: H Ä R + a fractional cover, a sufficient condition is given to ensure that the edge cover number (H), i.e., the size of a smallest set of edges of H with union V(H), is asymptotically at most t(H)= A # H t(A). This settles a conjecture first publicized in Visegra d, June 1991. 1997 Academic Press 1. INTRODUCTION This paper considers the interplay of integral and fractional behaviour of matching and covering problems in hypergraphs of bounded edge size. As observed in [20, 23], one may regard the fundamental results of V. Ro dl article no. TA972761 199 0097-3165Â97 25.00