The Rectangle Covering Number of Random Boolean Matrices

Abstract

The rectangle covering number of an $n$-by-$n$ Boolean matrix $M$ is the smallest number of 1-rectangles which are needed to cover all the 1-entries of $M$. Its binary logarithm is the Nondeterministic Communication Complexity, and it equals the chromatic number of a graph $G(M)$ obtained from $M$ by a construction of Lovasz and Saks.

We determine the rectangle covering number and related parameters (clique size, independence ratio, fractional chromatic number of $G(M)$) of random Boolean matrices, where each entry is 1 with probability $p = p(n)$, and the entries are independent.