The rectangle covering number of random Boolean matrices (Q2363099)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6744554
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | The rectangle covering number of random Boolean matrices |
scientific article; zbMATH DE number 6744554 |
Statements
The rectangle covering number of random Boolean matrices (English)
0 references
13 July 2017
0 references
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.
0 references
random graphs
0 references
graph coloring
0 references
communication complexity
0 references
0 references
0.8717174
0 references
0.8713634
0 references
0.8707116
0 references
0.8692449
0 references
0.8661537
0 references
