4
$\begingroup$

This problem originates from the tiling lowerbound method for communication complexity. In that method, there is a 0-1 matrix $M_{n \times n}$. A rectangle is defined as a submatrix $A \times B$ where $A \subseteq \{0,1\}^n$ and $B \subseteq \{0,1\}^n$. A rectangle is said to be monochromatic if all its elements are 0 (or all are 1). Define the minimum number of monochromatic rectangles needed to tile the whole matrix $M$ as $\chi$.

But the tiling defined as above might be difficult to visualize. For example, consider

$\begin{bmatrix} 1 0 1 0 \\ 0 0 0 0 \\ 1 0 1 0 \\ 0 0 0 0 \end{bmatrix}$

At first glance it might be that $\chi$ is very large. But after permuting the second and third row/column, we have

$\begin{bmatrix} 1 1 0 0 \\ 1 1 0 0 \\ 0 0 0 0 \\ 0 0 0 0 \end{bmatrix}$

then $\chi$ is easily seen to be 3 (since permutation doesn't change $\chi$).

To ease visulization, we define a contiguous rectangle as a rectangle with additional requirement that both $A$ and $B$ are contiguous. (For ex. $\{1,2,3\}$ is contiguous but $\{1,3,4\}$ isn't.) Assume $M'$ is formed from $M$ by a row/column permutation (which means you can permute any rows and any columns of $M$). Define $\chi'(M')$ as the mininum number of contiguous rectangles needed to tile $M'$. Define $\chi' = \min\{\chi'(M')$ | for any $M'\}$. The question is:

Is $\chi$ = $\chi'$?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ Why aren't the two examples above good enough to disprove $\chi = \chi'$? They have the same $\chi$ and different $\chi'$. $\endgroup$
    – Peter Shor
    May 25, 2011 at 12:33
  • 4
    $\begingroup$ You were interested in square matrices, but it seems that at least in the general case it should be easy to show that the answer is "no". For instance, the $2 \times 4$ matrix with the rows 0011 and 0101 can be tiled with 4 non-contiguous rectangles, but it seems that no matter how you permute the rows and columns, you need at least 5 contiguous rectangles. $\endgroup$
    – Jukka Suomela
    May 25, 2011 at 16:48
  • 5
    $\begingroup$ If you add two rows consisting of 0000 to @Jukka's 2 x 4 matrix, you get a 4 x 4 counterexample. You need at least 6 contiguous rectangles for this matrix. There is a unique column containing two 0's and two 1's. The tiling contains at least one rectangle covering the two 0's this column, and if you throw this rectangle away, you get a tiling of Jukka's matrix with at least one fewer rectangle. $\endgroup$
    – Peter Shor
    May 25, 2011 at 17:54
  • 3
    $\begingroup$ I wonder if one or both of these comments should be answers so that they can be accepted and the Community ghost doesn't keep floating this question up $\endgroup$
    – Suresh Venkat
    May 25, 2011 at 19:34
  • 3
    $\begingroup$ Perhaps @cyker could put together the comments, double-check it, fill in the missing details, write an answer, and accept it? $\endgroup$
    – Jukka Suomela
    May 25, 2011 at 20:03

1 Answer 1

Reset to default
6
$\begingroup$

As can be seen in the comments, Jukka provides a $2 \times 4$ counter example, which is further generalized by Peter to $4 \times 4$ to meet the requirements. Both analysis and program verification (use dynamic programming to calculate $\chi'$) can be performed to make sure $\chi \neq \chi'$ is possible when $n = 4$.

Actually Peter's generalization can be used to show there is an $n \times n$ matrix s.t. $\chi \neq \chi'$ for any $n$. The counter example is shown below:

$\begin{bmatrix} 1 1 0 0 0 \cdots 0 \\ 0 1 1 0 0 \cdots 0 \\ 0 0 0 0 0 \cdots 0 \\ 0 0 0 0 0 \cdots 0 \\ \vdots \\ 0 0 0 0 0 \cdots 0 \end{bmatrix}$

There's a unique column with two 1's. At least one continuous rectangle is needed to cover the 0's in this column. And this continuous rectangle doesn't cover any elements in the two rows corresponding to the two 1's. Remove this continuous rectangle and the rest will be a $2 \times n$ matrix:

$\begin{bmatrix} 1 1 0 0 0 \cdots 0 \\ 0 1 1 0 0 \cdots 0 \end{bmatrix}$

which needs at least 5 continuous rectangles to cover. So $\chi' \geq 6$. However, it is easy to see $\chi \leq 5$. So $\chi \neq \chi'$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Let's not forget that the question makes little sense in terms of communication complexity. The notions of being continuous or geometrical in terms of rectangles are mostly misleading. Unless you can SHOW that these are the only interesting rectangles! Which might be true in some sense. $\endgroup$
    – Hartmut Klauck
    May 26, 2011 at 17:31
  • 1
    $\begingroup$ can you accept this if it works: so that the question doesn't come up later ? $\endgroup$
    – Suresh Venkat
    May 26, 2011 at 22:56
  • $\begingroup$ @ Suresh Not until 7 hours later... $\endgroup$
    – Cyker
    May 27, 2011 at 0:51
  • $\begingroup$ @ Hartmut Continuous rectangles are easy to view. So in some sense they're preferred if possible, i.e., there's a row/col permutation which makes $\chi = \chi'$. Intuitively, unrestricted rectangles are much powerful than continuous ones so this might be impossible. And the answer to this question just verifies this. $\endgroup$
    – Cyker
    May 27, 2011 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.