Fractional v. Integral Covers in Hypergraphs of Bounded Edge Size

Jeff Kahn, P. Mark Kayll

Research output: Contribution to journalArticlepeer-review

Abstract

In the early 1980's, V. Rödl proved the Erdos-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 Rödl, by N. Pippenger, and by others. In each case, an appropriatesemi-randommethod 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-calledhard-coredistributions on the set of matchings of a graph. For fixedk≥2, H ak-bounded hypergraph, andt: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 unionV(H), is asymptotically at mostt(H)=∑A∈Ht(A). This settles a conjecture first publicized in Visegrád, June 1991

Original languageEnglish
Pages (from-to)199-235
Number of pages37
JournalJournal of Combinatorial Theory. Series A
Volume78
Issue number2
DOIs
StatePublished - May 1997

Fingerprint

Dive into the research topics of 'Fractional v. Integral Covers in Hypergraphs of Bounded Edge Size'. Together they form a unique fingerprint.

Cite this