The Rectangle Covering Number of Random Boolean Matrices

[摘要] 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

[学科分类] 离散数学和组合数学

[关键词] Random graphs;Graph coloring;Communication complexity