## DIMACS TR: 95-55

## Asymptotically Good Covers in Hypergraphs:
Extended Abstract of the Dissertation

### Author: P. Mark Kayll

**
ABSTRACT
**

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.

FOOTNOTE

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