Sets of points containing permutations - a Ramsey-type question

Question

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$ of $[n]$ means that: there are points $(x_1, y_1), \dots, (x_n,y_n) \in X$, such that $y_1<y_2<y_3<\dots<y_n$, and $x_i$ have the same relative ordering as $\sigma_i$ (meaning: $\sigma_i < \sigma_j \iff x_i < x_j$, for all $i,j$).

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 (construction: L-shape thinner than n/2).
• If $n/2$ bound holds, it is best possible (construction: color left half black, right half white).

Answer 1

Take a $3k\times 3k$ square, divide it into 9 congruent squares and paint as $$ \begin{array}{|c|c|c|} \hline B&B&W\\ \hline W&B&W\\ \hline W&B&B\\ \hline \end{array} $$ Fisrtly, we mention that it contains no black $(k+1)$-permutation $(1,2,\dots,k+1)$ and no white $(k+1)$-permutation $(k+1,k,\dots,1)$.

Next, it contains no monochromatic $(k+2)$-permutation $(2,k+2,\hbox{(anything)},1,k+1)$.

So, if a square should contain every $t$-permutation in a monochromatic way, its side should be of order at least $3t$. In fact, it seems that this order should be superlinear.

Answer 2

If partial results are fair game then observe that, for every $2$-colouring of $[n^2]^2$, one of the colour classes contains all of the permutations on $n$ points. Indeed, view $[n^2]^2$ as an $n \times n$ grid, each entry of which is itself an $n \times n$ grid. If any small grid is all white then it contains all permutations on $n$ points. Otherwise every small grid contains at least one black point, and these $n^2$ black points contain all permutations on $n$ points.

Answer 3

Here is the sketch of an argument that I heard from Martin Balko.

It seems to show that the correct asymptotics is $N(k) = k^2 / polylog(k)$. That is, there is a B/W coloring of the $N(k) \times N(k)$ grid such that some permutation of size $k$ is not contained in either the B or the W sets. If true, then this is quite close to the upper bound of Ben Barber from the other answer.

The argument uses a result from the recent paper Ordered Ramsey Numbers by Conlon, Fox, Lee, and Sudakov (http://arxiv.org/abs/1410.5292).

Theorem 2.4 of the paper claims (essentially) the following. For all $k$, there is some value $N = k^2 / polylog(k)$ and some perfect matching $M$ of a bipartite graph with vertices $L = \{1,...,k\}$, and $R = \{k+1,...,2k\}$, such that we can color B/W the edges of a complete graph $H$ with vertices $\{1,...,N\}$ such that $M$ is not contained either as a B-subgraph, or as a W-subgraph. Here, ``contained'' means that the vertices of $M$ are mapped to vertices of $H$ such as to respect the ordering.

Our problem is essentially the same, with the difference that $H$ is a complete bipartite graph with vertices, say $\{1,...,N/2\}$ and $\{N/2+1,...,N\}$. This can be seen as deleting some of the edges of $H$, or coloring them with some third color that we can not match to anything. Denote the resulting graph as $H'$. If some matching was not contained in $H$, then it is also not contained in $H'$, i.e. by going from the complete to the complete bipartite graph, avoiding some subgraph becomes easier.

Note: $H'$ plays the role of the matrix, and the ordered matching $M$ plays the role of the contained (or avoided) permutation.

It would be nice to get some intuition how such a coloring looks "visually" -- from the proof in the paper it is hard to get such an intuition.

Answer 4

Regarding the weak version, I can prove that there exists an $f$ such that for every two colouring of the $f(n) \times f(n)$ grid, every permutation of $[n]$ is contained in either $B$ or $W$. The proof leaves a lot of room for optimization, so perhaps one can get down to $f=2n$.

Proof. Evidently, $f(1)=1$ works. We then define $f$ recursively via $f(n+1)=(n+2)(f(n)+1)+1$. Consider a 2-colouring of the $f(n+1) \times f(n+1)$ grid $G$ and suppose that some permutation $\sigma$ of $[n+1]$ does not appear in either $B$ or $W$. Let $\sigma'$ be the permutation of $[n]$ obtained by removing $n+1$ and $\sigma(n+1)$ from $\sigma$ and then renaming $[n+1] \setminus \sigma(n+1)$ according to their relative order.

Let $G'$ be the subgrid of $G$ containing the entry $(1,1)$ and with horizontal and vertical entries spaced $n+1$ entries apart. By choice of $f$ we have that $G'$ is a $(f(n)+2) \times (f(n)+2)$ grid. Let $G''$ be the subgrid of $G'$ obtained by removing the boundary entries. Thus, $G''$ is a $f(n) \times f(n)$ grid. By induction, $G''$ contains a black copy of $\sigma'$ or a white copy of $\sigma'$. Assume it is black. Let $G_1, \dots, G_{n+1}$ be the $(n+1) \times (n+1)$ blocks of $G$ between the last two columns of $G'$. Note that every entry of $G_{\sigma(n+1)}$ must be white, otherwise, $G$ contains a black $\sigma$. But now $G_{\sigma(n+1)}$ contains a white copy of every permutation of $[n+1]$.