In communication complexity one important object is the combinatorial retangle. Given a $0-1$ square matrix $M$, do their exist permutations $\sigma,\pi$ such that $\sigma M\pi$ consists of only geometric rectangles? That is all the combinatorial rectangles are geometrically connected?
2
$\begingroup$
$\endgroup$
4
$\begingroup$
$\endgroup$
It's not possible. Consider the following 3x3 boolean matrix:
1 1 0
1 0 1
0 1 1
For every pair of rows {r,r'} , there exists a column c such that {r,r'} X {c} is a combinatorial rectangle. For any particular pair, we can permute the rows such that {r,r'} are adjacent. However, since we have a combinatorial rectangle for all pairs of rows, it's not possible to permute the rows so that all such rectangles are geometrically connected simultaneously.
