# combinatorial rectangles

Consider the set $S$ of all $m\times m$ matrices with $0-1$ entries with exactly $T$ combinatorial rectangles of all $0$s or all $1$s that partition each matrix in a non-overlapping manner.

Is there a $2^{\log_2^{c_T} m}\times 2^{\log_2^{c_T} m}$ matrix $A$ such that every element in $S$ occurs as a combinatorial rectangle (possibly overlapping) in $A$ and $A$ can be partitioned with exactly $T^{d_T}$ combinatorial rectangles of all $0$s or all $1$s in a non-overlapping manner?

Combinatorial rectangle is a subset of all elements in a matrix indexed by a certain subset of rows and a certain subset of columns.

${c_T},{d_T}$ are some positive constants that vary with $T$.

• Your proposed bound $2^{\log_2^{c} m}$ does not depend on $T$. So what stops us from taking $S$ to be all binary matrices? – Sasho Nikolov Nov 19 '14 at 6:45
• @SashoNikolov modified! – ASF Nov 19 '14 at 6:48