Improved Bounds for Multicovering Hypergraphs

Anand Babu, Sundar Vishwanathan

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$…