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.

  • $\begingroup$ can you provide the argument for $c<1/2$ as part of the question? $\endgroup$ – 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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.