Given a Cartesian product of sets $X \times Y$, A (combinatorial) rectangle is a set $A \times B$ where $A \subseteq X$ and $B \subseteq Y$. Given a function $f : X \times Y \rightarrow \{ 0, 1\}$ one can obviously arrange this into a n |X| by |Y| matrix $M_f$. A rectangle $A \times B$ is called monochromatic if $f((x, y)) = z \in \{0, 1\}$ for all $(A,B) \in A \times B.$
Let t(f) denote the minimum number of monochromatic rectangles to cover f and let p(f) denote the min number to partition. can anybody think of a matrix where t(f) < p(f)? I literally can't...
many thanks!
Any partition also constitutes a cover. The only difference between a covering and a partition is that in a partition the rectangles used don't overlap. Since every partition is also a cover then it is clear $t(f)\leq p(f)$.
Perhaps a more interesting question would be if it is possible for $t(f)<p(f)$ there are cases, consider the following matrix where $X=\{a,b,c\}$ and $Y=\{\alpha,\sigma,\beta\}$ and where the matrix associated to $f$ is
$ \begin {bmatrix} 0&0&1\\ 0&0&0\\ 1&0&0\\ \end{bmatrix} $
Clearly you will need 2 rectangles to cover the ones. And if you don't want overlapping tiles you will need 3 rectangles to cover the zeros. However if you can overlap you only need 2 rectangles (the two $2\times2$ squares do the trick).