Ramsey type theorem for polygons on lattices

Question

It's not difficult to show that given a 2-coloring of the lattice $L:=\{1,2,3\} \times \{1,\dots,9\} \subseteq \mathbb Z^2$ we find a monochromatic rectangle in $L$. Generalizing, for any $r$-coloring on $\mathbb Z^2$ can we always find a lattice $L \subseteq \mathbb Z^2$ containing a given monochromatic polygon? How large is a minimal $L$?

Answer 1

A large enough lattice definitely always exists, but how large exactly depends on the specifics of the problem.

Either way, it's a good idea to reduce the 'monochromatic polygon' problem to a 'monochromatic sublattice' problem as follows: given vertices $(x_1, y_1), \dots, (x_k, y_k)$ of a canonical instance of this polygon, define the sublattice $S$ to be $S := \{x_1, \dots, x_k\} \times \{y_1, \dots, y_k\}$. Example: $$P = \begin{Bmatrix} & (1,2) & (1,3) \\ (2,1) & & (2,3) \\ & (3,2) \end{Bmatrix}\qquad \Longrightarrow \qquad S = \begin{Bmatrix} (1,1) & (1,2) & (1,3) \\ (2,1) & (2,2) & (2,3) \\ (3,1) & (3,2) & (3,3) \end{Bmatrix}$$ If we find a monochromatic copy of $S$, then we find a monochromatic copy of $P$.

What we mean by a "copy of $S$" depends on what "copy of $P$" meant. In the case of the polygon $P$ given above, is any polygon with vertices $\{(x_1, y_2), (x_1, y_3), (x_2, y_1), (x_2, y_3), (x_3, y_2)\}$ a copy of $P$? Or is it important that $|x_1 - x_2| = |x_2 - x_3|$, and that $|y_1 - y_2| = |y_2 - y_3|$? Should we also ask that $|x_1 - x_2| = |y_1 - y_2|$?

---

The first version is the most forgiving, and in this case, any sublattice with the same number of rows and columns as $S$ should be considered a "copy of $S$".

We can solve this in basically the exact same way as the rectangle problem. Say we're looking for a copy of a $k \times \ell$ lattice $S$. Then just take the large lattice $L$ to be $kr \times \ell r\binom{kr}{r}$. This has a monochromatic copy of $S$ in it, since:

• In each column, at least $k$ points must receive the same color.
• There are $r\binom{kr}{r}$ ways to say which $k$ points and which color that is, and $\ell$ times as many columns, so at least $\ell$ columns have the same $k$ points repeated in the same color.
• This is a monochromatic copy of $S$.

I'm being slightly sloppy with the pigeonhole here, and we're also giving away a lot with the polygon to sublattice reduction. But the result is still polynomial in $k$ and $\ell$ for a fixed $r$, which is pretty good.

---

The least permissive version of the sublattice problem (which should find you copies of a polygon in any sense of the word "copy") is when we're looking for a $k \times \ell$ sublattice in which the distances between any two adjacent rows or columns are all equal. For the purposes of symmetry, let's make this a $t \times t$ sublattice, where $t = \max\{k,\ell\}$.

This can be reduced to the Hales–Jewett theorem (again, in much the same way that the monochromatic square problem can be reduced to Hales–Jewett). Take the $n$-dimensional grid $\{1,2,\dots,t^2\}^n$ and "flatten it out" into a lattice recursively: think of this grid as $t^2$ copies of the $n-1$-dimensional grid $\{1,2,\dots, t^2\}^{n-1}$ (parametrized by the first coordinate) and arrange their flattened-out versions in a $t \times t$ square. For example, for $t=2$ and $n=3$, we get $$ \begin{matrix} 111 & 112 & 121 & 122 & 211 & 212 & 221 & 222 \\ 113 & 114 & 123 & 124 & 213 & 214 & 223 & 224 \\ 131 & 132 & 141 & 142 & 231 & 232 & 241 & 242 \\ 133 & 134 & 143 & 144 & 233 & 234 & 243 & 244 \\ 311 & 312 & 321 & 322 & 411 & 412 & 421 & 422 \\ 313 & 314 & 323 & 324 & 413 & 414 & 423 & 424 \\ 331 & 332 & 341 & 342 & 431 & 432 & 441 & 442 \\ 333 & 334 & 343 & 344 & 433 & 434 & 443 & 444 \end{matrix} $$ A combinatorial line in the $n$-dimensional grid will translate to a $t\times t$ sublattice of this lattice. So all we need is to choose $n$ to be at least the Hales–Jewett number $\operatorname{HJ}(r,t^2)$ and then we can find a $t\times t$ sublattice inside any $r$-coloring of the $t^n \times t^n$ lattice.

This is a very large upper bound, but necessarily so, given that this version of the polygon problem can have finding arbitrarily long monochromatic arithmetic progressions as a subtask.