We say a matrix $(a_{ij})$ is 0-1 matrix if $a_{ij}\in \{0,1\}$ for all $i,j$. We say a matrix $(a_{ij})$ is monochromatic if for some $a$, $a_{ij} = a$ for all $i,j$.
Question: Let $c\geq 1/2$ be a constant and $n$ be very large. Given a $n\times n$ 0-1 matrix $M$, must there be a $c\log_2 n\times c\log_2 n$ submatrix $M'$ of $M$ that is monochromatic?
When $c<1/2$ such submatrix $M'$ clearly exists (see below) but we wonder the case of $c\geq 1/2$.
The case $c<1/2$: It suffices to construct a $2c \log_2 n\times 2c \log_2 n$ matrix $\hat{M}$ so that each row of $\hat{M}$ is monochromatic (but different row may have different "color"). The row of $\hat{M}$ is simply the first $2c \log_2 n$ rows of $M$. To select columns of $\hat{M}$, inductively screen out columns of $M$. The first row screen out a set $K$ of columns of $M$ with $|K|\leq n/2$ where $a_{0j} = a$ for all $j\in K$ and $a_{0j} = 1-a$ for all $j\notin K$. The second row screen out a set $K'\subseteq K$ of columns with $|K'|\leq |K|/2$ where $a_{1j} = a'$ for all $j\in K'$ and $a_{1j} = 1-a'$ for all $j\in K\setminus K'$. Keep doing this for each rows of $\hat{M}$ (which is $2c\log_2 n$ many times) and there will be at least $n^{1-2c}$ many columns remained.
