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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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