Improved Bounds for Multicovering Hypergraphs

Abstract

The minimum number of bicliques needed to cover the edge set of the complete graph on $n$ vertices is $\lceil {\log }_{2}n\rceil$. The Graham-Pollak theorem states that at least $n-1$ bicliques are required to partition the edge set of the complete graph on $n$ vertices. In this paper, we provide improvements for the generalizations of coverings of graphs and hypergraphs for some specific multiplicities. We also study an extension of the Katona-Szemerédi theorem to $r$-uniform hypergraphs.

11 pages