The following question arised as a side-question in a geometric problem. It has a "feel" similar to problems in Ramsey-theory, but I have not found any mention of it (also I'm not very familiar with the field). Was this problem considered before? Does it have an easy answer?

Consider the set of grid points $[n] \times [n]$, and color each point either black or white, giving rise to the sets $B,W$ (such that $B \cup W = [n] \times [n]$, and $B \cap W = \emptyset$).

Are the following true?

• (stronger): Either $B$ or $W$ contains every permutation of $[n/2]$.

• (weaker, implied by stronger): Every permutation of $[n/2]$ is contained in either $B$ or $W$.

• if true, holds also for $k$ colors and $n/k$? if not true, what is largest $m$ for which it holds?

A set of points $X$ containing a permutation $\sigma$ means the following: there are points $(x_i, y_i) \in X$, such that $y_1<y_2<y_3<\dots$, and $x_i$ have the same relative ordering as $\sigma_i$. For example, $[n] \times [n]$ contains all permutations of $[n]$.

Some easy observations:

• One of $B$ and $W$ might not contain all permutations, even if it contains more than half of the original points.
• If $n/2$ bound holds, it is best possible (construction: color left half black, right half white).