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.
@article{10_37236_5576,
author = {Mozhgan Pourmoradnasseri and Dirk Oliver Theis},
title = {The rectangle covering number of random {Boolean} matrices},
journal = {The electronic journal of combinatorics},
year = {2017},
volume = {24},
number = {2},
doi = {10.37236/5576},
zbl = {1415.05167},
url = {http://geodesic.mathdoc.fr/articles/10.37236/5576/}
}
TY - JOUR
AU - Mozhgan Pourmoradnasseri
AU - Dirk Oliver Theis
TI - The rectangle covering number of random Boolean matrices
JO - The electronic journal of combinatorics
PY - 2017
VL - 24
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/5576/
DO - 10.37236/5576
ID - 10_37236_5576
ER -
%0 Journal Article
%A Mozhgan Pourmoradnasseri
%A Dirk Oliver Theis
%T The rectangle covering number of random Boolean matrices
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/5576/
%R 10.37236/5576
%F 10_37236_5576
Mozhgan Pourmoradnasseri; Dirk Oliver Theis. The rectangle covering number of random Boolean matrices. The electronic journal of combinatorics, Tome 24 (2017) no. 2. doi: 10.37236/5576
