For any bipartite graph $G=(L\cup R,E)$ with $|L|=|R|=n$, can we always choose subsets $L_1\subseteq L$ and $R_1\subseteq R$ with $|L_1|=|R_1|=n/c$, such that either $\forall~l\in L_1 ~\forall r\in R_1, (l,r)\in E$, or $\forall ~l\in L_1 \forall~ r\in R_1, (l,r)\notin E$ for some constant $c$?
It is known that $c=2$ does not hold. The counterexample is as follows: Denote $L=R=\{0,1,\cdots,n-1\}$, then $(i,j)\in E$ if and only if $(j-i)\bmod n< n/2$.
I guess it is true for $c=4$, but have no idea how to prove or disprove it.
OK, using random graph to prove a negative result: $n/c$ is not possible; $O(\log n)$ is the maximum size of $L$ and $R$.