Partition Number of a Matrix Given matrix $M\in\{0,1\}^{n\times n}$, let the minimum number of monochromatic rectangles it can be partitioned be $p$. Let the positive rank of $M$ be $\sigma$ and the rank be $r$. Is it known either $$p&lt;r^{\log^dr}\mbox{ or }p&lt;\sigma^{\log^c\sigma}\mbox{ or }p&lt;(\sigma^{\log^c\sigma}r^{\log^dr})$$ hold true for some $c,d&gt;0$?

Can $p&lt;\sigma^{c}$ be true?
The log of the partition number is a lower bound on the deterministic communication complexity and the square of the log of the partition number is an upper bound. In other words, if $CC$ is the communication complexity, then we know that $\log_2 p \leq CC \leq (\log_2 p)^2$: this is Theorem 2.11. in the Kushilevitz-Nisan monograph. It is an open problem whether $CC = \Theta(\log p)$, and the biggest known gap is a factor $2$.

So $p &lt; r^{\log^d r}$ for a constant $d$ implies that the communication complexity is at most $\log^{2d+2} r$. In other words there exists such a constant $d$ if and only if the log rank conjecture is true. I believe the best we know is $p &lt; r^{C\sqrt{r}}$ for a constant $C$, by a recent result of Lovett.