TY - JOUR
T1 - Fractional v. Integral Covers in Hypergraphs of Bounded Edge Size
AU - Kahn, Jeff
AU - Kayll, P. Mark
N1 - Funding Information:
* Supported in part by NSF. E-mail: jkahn math.rutgers.edu. -This work forms part of the author’s doctoral dissertation [28]; see also [29]. The author gratefully acknowledges NSERC for partial support in the form of a 1967 Science and Engineering Scholarship. E-mail: kayll charlo.math.umt.edu.
PY - 1997/5
Y1 - 1997/5
N2 - 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
AB - 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
UR - http://www.scopus.com/inward/record.url?scp=0010753118&partnerID=8YFLogxK
U2 - 10.1006/jcta.1997.2761
DO - 10.1006/jcta.1997.2761
M3 - Article
AN - SCOPUS:0010753118
SN - 0097-3165
VL - 78
SP - 199
EP - 235
JO - Journal of Combinatorial Theory. Series A
JF - Journal of Combinatorial Theory. Series A
IS - 2
ER -