How can we apply Ramsey's theorem to solve this problem on matrices?

Question

This is from a problem set in a combinatorics course I am taking, and reads as follows:

Let $m\geqslant 1$ be an integer. Prove there exists an $n\geqslant 1$ with he following property: every $M\in \{0,1\}^{n\times n}$ has a principal $m\times m$ submatrix that has all its diagonal elements equal, and all subdiagonal elements equal. Principal means the matrix is obtained from $M$ by deleting $n-m$ columns, and the same rows (i.e. if we delete row $i$, we delete with it column $i$ too).

This clearly suggests the use of (some of the various) Ramsey's theorem. Note that taking an $m\times m$ principal amounts to choosing $m$ elements of the diagonal, and since we want all element of the diagonal to be the same, we know that $n\geqslant R(m,m;1)=2m-1$.

However, I cannot think on what kind of coloring to define that will yield the result. Could anyone give a hint, and maybe give an idea on how to approach this kind of problems?

Answer 1

I think the following hint will help you solving it.

Forget one instant about the diagonal restriction. So you just want a principal $m\times m$ submatrix such that the subdiagonal elements are equal. Now think about the adjacency matrix of a graph, remember that it is symmetric. What does it mean to have a principal $m\times m$ submatrix, with all $1$'s (or $0$'s) in the subdiagonal, in the adjacency matrix of a graph?

Then you have to add the diagonal restriction.

Answer 2

Here's the solution based on the hint.

Suppose $G$ is a graph on $n$ vertices and $M\in \{0,1\}^{n\times n}$ is its adjacency matrix, let $v_1,\ldots,v_n$ be the vertices of $G$. Deleting the $i$-th row and $i$-th column amounts to looking at the induced graph $G[V-v_i]$. Thus obtaining an $m\times m$ principal with all subdiagonal elements equal in an adjacency matrix amounts to finding a set of $m$ vertices that form a $K_m$ in $G$ or a $K_m$ in the complement of $G$. Now choose $N=2 R(m,m;2)-1$. We have $N$ diagonal elements which are $1$ or $0$, so there are at least $ R(m,m;2)$ zeroes or $ R(m,m;2)$ ones in the diagonal. Suppose there are $N'=R(m,m;2)$ ones. If we look at the submatrix obtained by deleting the other diagonal elements, we have an $N'\times N'$ matrix of zeroes and ones. By looking under the diagonal, we obtain the adjacency matrix of a graph on $N'$ vertices. By definition of $R(m,m;2)$ there is either a subgraph that is a $K_m$ in $G$ or a subgraph that is a $K_m$ in the complement. In any case, deleting the other diagonal entries (vertices) we get a matrix of size $m\times m$ which has all diagonal elements and all subdiagonal elements equal, as desired.

ADD I realized I misread the problem, and the matrix has to have elements under the diagonal all equal and over (not on) the diagonal all equal. One can see the number $R(R(m,m;2),R(m,m;2);2)$ works by a similar argument as above: looking over the diagonal first, the defintions of Ramsey's number gives a complete graph on $R(m,m;2)$ vertices or one on the complement, i.e. all zeroes over the diagonal, or all $1$s. Then we have a matrix of size $R(m,m;2)$ with all zeroes or ones over the diagonal, and by definition of Ramsey's number we get a complete graph on $m$ vertices or one on the complement, so a principal matrix of size $m\times m$ with all zeroes or all ones over the diagonal and all zeroes or all ones over the diagonal, as we wanted.