DIMACS TR: 95-55

Asymptotically Good Covers in Hypergraphs: Extended Abstract of the Dissertation

Author: P. Mark Kayll


In the early 1980's, V. R\"{o}dl proved the Erd\H{o}s-Hanani Conjecture, sparking a remarkable sequence of developments in the theory of packing and covering in hypergraphs with bounded edge size. Generalizations were given by P. Frankl and R\"{o}dl, by N. Pippenger, and by others. In each case, an appropriate {\em semirandom} method was used to ``construct'' the desired optimal object (covering, matching, coloring) 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 {\em normal} distributions on the set of matchings of a graph. For fixed $k\geq 2$, ${\cal H}$ a $k$-bounded hypergraph, and $t:{\cal H}\rightarrow \mbox{{\bf R}}^+$ a fractional cover, a sufficient condition is given to ensure that the edge cover number $\rho({\cal H})$, {\em i.e.}, the size of a smallest set of edges of ${\cal H}$ with union $V({\cal H})$, is asymptotically at most $t({\cal H}) = \sum_{A\in {\cal H}}t(A)$. This settles a conjecture first publicized in Visegr\'{a}d, June 1991.


The paper (and the dissertation upon which it is based) was written while the author was a DIMACS-affiliated mathematics graduate student of Jeff Kahn. Both the paper and the dissertation were written using the DIMACS Sun terminal room. DIMACS was acknowledged in the author's dissertation, which should now be in the Rutgers math library. It seems appropriate to include the extended abstract in the DIMACS technical report series as well.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-55.ps.gz

DIMACS Home Page