Covering non-uniform hypergraphs

A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let, tau (H) denote the cardinality of a minimum cover in the hypergr aph H, and let us denote by g(n) the maximum of tau (H) taken over all hype rgraphs H with n vertices and with no two hyperedges of the same size. We s how that g(n) < 1.98 rootn(1 + o(1)). A special case corresponds to an old problem of Erdos asking for the maximu m number of edges in an n-vertex graph with no two cycles of the same lengt h. Denoting this maximum by n + f(n), we can show that f(n) less than or eq ual to 1.98 rootn(1 + o(1)). Generalizing the above. let g(n. C, k) denote the maximum of tau (H) taken over all hypergraph H with n vertices and with at most Ci(k) edges with cardinality i for all i = 1. 2...., n. We prove t hat g(n, C. k) < (Ck! + 1) n((k + 1)/(k + 2)) These results have an interesting graph-theoretic application. For a family F of graphs, let Tin, F. r) denote the maximum possible number of edges in a graph with n vertices. which contains each member of F at most r - 1 tim es. T(n, F, 1) = T(n, F) is the classical Turan number. Using the results a bove, we can compute a non-trivial upper bound for T(n, F, r) for many inte resting graph families. (C) 2001 Acadmic Press.