The rectangle covering number of random Boolean matrices (Q2363099): Difference between revisions

Summary: The rectangle covering number of an \(n \times 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_\boxtimes(M)\) obtained from \(M\) by a construction of \textit{L. Lovász} and \textit{M. Saks} [J. Comput. Syst. Sci. 47, No. 2, 322--349 (1993; Zbl 0791.68083)]. We determine the rectangle covering number and related parameters (clique size, independence ratio, fractional chromatic number of \(G_\boxtimes(M)\)) of random Boolean matrices, where each entry is 1 with probability \(p = p(n)\), and the entries are independent.