# Every point of a grid is colored in blue, red or green. How to prove there is a monochromatic rectangle?

I have a $3$-coloring of $\mathbb{Z}\times\mathbb{Z}$, i.e. a function $f:\mathbb{Z}\times\mathbb{Z}\to\{\color{red}{\text{red}},\color{green}{\text{green}},\color{blue}{\text{blue}}\}$.

I have to prove that there is a monochromatic rectangle with its sides being parallel to the axis, i.e. to prove that for some choice of $a,b,c,d\in\mathbb{Z}$ with $a\neq b$ and $c\neq d$, all the points $(a,c),(a,d),(b,c),(b,d)\,$ have the same color.

I tried to work by contradiction, without achieving much.

Additionally, can we prove some upper bound on $|a-b|$ and $|c-d|$?

• Every point of what is colored? – Arthur Sep 8 '16 at 16:22
• Of a graph... You know the one where all spaces are squares... How do you call them? – user366454 Sep 8 '16 at 16:24
• @Jack's edit makes this question! Wish I could upvote edits... – alexis Sep 8 '16 at 20:17
• The idea in Joffan's answer can be used to construct a $4 \times 18$ grid that doesn't have a monochromatic rectangle. And clearly there's such a $3 \times n$ grid for any $n$ (use one colour per row). So what's left is to solve this for grids of size $m \times n$ where $4<m\leq n \leq 18$. – JiK Sep 9 '16 at 9:11
• There is no monochromatic rectangle in an infinite chessboard except for the trivial case of size=1. Considering the answers and the rest of the question I would change "monochromatic rectangle" to "rectangle where the four corner points are monochromatic". – Anonymous Coward Sep 9 '16 at 14:05

Such a rectangle will occur in a grid of $19$ columns by $4$ rows.

By the pigeonhole principle, each column must have a repeated colour point. Ignoring any later repeats, classify the columns according to the first two repeat colour positions; there are $6$ options: $(1,2), (1,3), (1,4), (2, 3), (2, 4)$ and $(3,4)$. So since there are also $3$ colour options for the repeated colours there are only $6\times3=18$ different options for repeated colour by position. Therefore, by the pigeonhole principle again, in a $19\times 4$ grid we must have a suitable rectangle with identically coloured corners.

From an observation by Pere in comments:

For $n$ colours, using the same approach, we would adopt a grid of $(n+1)$ rows and then require $n{n+1 \choose 2}+1 = n(n+1)n/2 +1 = (n^3+n^2)/2 + 1$ columns to find a rectangle with same-coloured corners.

• Pigeonhole principle FTW :-). One of my favorite tools in 'restricted counting' -type problems. – Carl Witthoft Sep 8 '16 at 19:42
• Is there a general formula for the case of n-colors? – Shufflepants Sep 8 '16 at 20:30
• @Shufflepants Following Joffan's reasoning, for an arbitrary n such a rectangle will occur in a grid of $(n^3+n^2)/2+1$ columns by $n+1$ rows. – Pere Sep 8 '16 at 20:35
• 4 rows is very obviously minimal, and one can also clearly avoid a monochromatic-cornered rectangle by taking the 18 distinct options you mention — but can someone show that every grid with fewer than $19*4=76$ points can be coloured without a m~-c~ r~? Elegantly? (P.S. I am pleased to report this answer currently has $38=19*4/2$ (net) votes up – but I am about to change that!) – PJTraill Sep 12 '16 at 14:38
• @PJTraill Interesting question. I had a different challenge in mind, whether there is a square 3-coloured grid smaller than $19 \times 19$ that also must have a mono-coloured rectangle. – Joffan Sep 12 '16 at 20:40

For a slightly more quantitative proof, we may show that there is a monochromatic rectangle with its largest dimension being $\color{red}{\leq 82}$ and its smallest dimension being $\color{red}{\leq 4}$.

Step 1. We may give to any integer point $(x,0)$ on the $x$-axis a maxi-color in the set $\{1,2,\ldots,80,81\}$ depending on the actual colors of $(x,0),(x,1),(x,2),(x,3)$.

Step 2. By the Dirichlet box principle, among $82$ consecutive lattice points on the $x$-axis at least two of them, say $(a,0)$ and $(b,0)$, have the same maxi-color.

Step 3. Since we have only three actual colors, at least two points among $(a,0),(a,1),(a,2),(a,3)$ have the same color. Such points, coupled with the corresponding points on $x=b$, give the wanted monochromatic rectangle.

The $82$ above can be replaced by a smaller number, namely $1+\alpha(G)$, i.e. one plus the size of the largest independent set in a quite complicated graph (of the Haggkvist-Hell type) on $81$ vertices. So we may also improve the given bound by using some rather deep results about topological graphs (see Kneser's conjecture, proved by Lovasz in 1978 through the Borsuk-Ulam theorem).

However, an elementary proof that $\alpha(G)=18$ is presented above by Joffan.

Theorem: Let $X,Y$ be infinite sets. If the points of $X\times Y$ are colored with a finite number of colors in such a way that there exists a set $C$ of $c$ colors such that for every $x\in X$ only colors in $C$ appear an infinite number of times among pairs of the form $(x,y)$, then there exist $x_1,x_2\in X,y_1,y_2\in Y$ so that $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ all have the same color.

Proof:

We proceed by induction on $c$, when $c=1$ it is clear. Take any $x_1,x_2$ and let $\alpha$ be the only color that appears an infinite number of times. Notice that the set of $A_{x_1}=\{y\in Y | (x_1,y) \text{ has color } \alpha\}$ has finite complement, and so does the set $A_{x_2}=\{y\in Y | (x_2,y) \text{ has color } \alpha\}$. This implies $A_{x_1}\cap A_{x_2}$ is infinite. Taking $x1,x2$ and any $y_1,y_2\in A_{x_1}\cap A_{x_2}$ does the trick.

Inductive step: Consider any $x\in X$, there must be an $\alpha \in Y$ such that the set $A_{x}=\{y\in Y | (x,y) \text{ has color } \alpha\}$ is infinite. Now consider the set $X'=X\setminus x$ and $Y'=A_x$. If there is an $x'\in X'$ such that there is an infinite number of $y'\in Y'$ such that $(x',y')$ has color $\alpha$ then we are done. just take $x,x'$ and $y_1,y_2$ such that $(x',y_1)$ and $(x',y_2)$ have color $\alpha$. Otherwise notice that the set $C'=C\setminus\alpha$ has $c-1$ elements, and for every $x\in X'$ the only colors that appear an infinite number of times among the pairs $(x,y)$ are in $C'$. By the inductive hypothesis there exist $x_1,x_2\in X'$ and $y_1,y_2\in Y'$ such that $(x_1,y_1),(x_1,y_2),(x_2,y_1),(x_2,y_2)$ all have the same color.

• I think that I'm not quite understanding your language. Is $C$ the set of finite- or infinite-multiplicity colours? You seem to say the former, but your base case seems to assume the latter. – LSpice Sep 8 '16 at 19:22
• Infinito, let me update – Jorge Fernández Hidalgo Sep 8 '16 at 19:27
• Definitely a Carl Gauss type of proof :-) i.e. very precise and formal, and equally difficult to connect to the real-world implementation. Not complaining, just comparing w/ the approach Joffan took. – Carl Witthoft Sep 8 '16 at 19:44
• Yeah right... I wish this was a Carl Gauss type of proof, thanks @CarlWitthoft – Jorge Fernández Hidalgo Sep 8 '16 at 20:12
• Minor point: I think $\alpha \in Y$ in the first sentence of the inductive step should say $\alpha in C$. Slightly more important, because it requires more effort to work out what it's supposed to say: "for every $x \in X'$ the only colors that appear an infinite number of times among the pairs $(x,y)$ are in $C'$" is missing the constraint $y \in Y'$. – Peter Taylor Sep 9 '16 at 10:04