Name
Abstract | ||
|---|---|---|
In the early 1980's, V. Rödl proved the Erdő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 Rö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 Visegrád, June 1991 |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1006/jcta.1997.2761 | J. Comb. Theory, Ser. A |
Keywords | Field | DocType |
fractional v,integral cover,bounded edge size | Discrete mathematics,Graph,Combinatorics,Generalization,Edge cover,Constraint graph,Hypergraph,Probabilistic logic,Conjecture,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
78 | 2 | Journal of Combinatorial Theory, Series A |
Citations | PageRank | References |
5 | 0.73 | 16 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Jeff Kahn | 1 | 5 | 0.73 |
| P. Mark Kayll | 2 | 65 | 8.34 |