2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Nov 19 '14 at 6:45
  • $\begingroup$ @SashoNikolov modified! $\endgroup$ – ASF Nov 19 '14 at 6:48

Your Answer

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

Browse other questions tagged or ask your own question.