Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\Big|$$ and biclique size given by $$\gamma(M)=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big\{\Big|\mathcal I\times\mathcal J\Big|:{ \forall (i,j)\in\mathcal I\times\mathcal J, \mbox{ each }M_{ij} \mbox{ is same (all }1\mbox{ or all }-1)}\Big\}.$$
Clearly $\gamma(M)\leq\|M\|_C$.
What is the maximum gap between $\gamma(M)$ and $\|M\|_C$ among all real $0/1$ or $\pm1$ matrices $M\in\Bbb R^{n\times m}$ of rank $r$?
Without $r$ in the picture the gap has to be exponential or else $P=NP$ holds since cut norm has constant factor approximation while biclique does not.
