# The size of monochromatic submatrix

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.

• can you provide the argument for $c<1/2$ as part of the question? – kodlu Aug 12 '20 at 7:35

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