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.



The size of monochromatic submatrix
Even $c=1-\varepsilon$ works when $n$ is large enough. This question is about bounding the diagonal bipartite Ramsey, see the recent achievement of David Conlon here
[http://people.maths.ox.ac.uk/~conlond/Bipartite.pdf](http://people.maths.ox.ac.uk/%7Econlond/Bipartite.pdf)


