16
$\begingroup$

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).
$\endgroup$
  • $\begingroup$ Have you run any computer experiments on this? $\endgroup$ – Per Alexandersson Jan 30 '15 at 15:14
  • $\begingroup$ No, it seemed like it should be true for some obvious reason (that I am missing), but it will be worth checking if a proof will not be found. $\endgroup$ – László Kozma Jan 30 '15 at 15:28
  • $\begingroup$ I don't know if this precise form is in the literature. Looking at permanents, binary matrices, and enumerating matrices avoiding a certain pattern may get you literature which gets close to the form above. $\endgroup$ – The Masked Avenger Jan 30 '15 at 16:37
  • $\begingroup$ Also I don't see the first easy observation: can you provide an example where B has more than half the nodes and not all the permutations of n/2? $\endgroup$ – The Masked Avenger Jan 30 '15 at 16:45
  • $\begingroup$ For the first observation, color the top-right square of size $(n/2+1) \times (n/2+1)$ white. The remaining B has almost $3/4$ of the points, yet it does not include the identity permutation. $\endgroup$ – László Kozma Jan 30 '15 at 16:49
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I think you must switch "black" and "white". $\endgroup$ – Wolfgang Jan 31 '15 at 9:29
  • $\begingroup$ Interesting. I wonder how low (k+l) can go, using the notation in Paseman's comment. $\endgroup$ – The Masked Avenger Jan 31 '15 at 18:03
  • 1
    $\begingroup$ Very nice, I think I will accept this answer, as it disproves the original n/2 conjecture of the question. But now it seems interesting to try narrowing the gap between this and the one from Ben Barber's answer. $\endgroup$ – László Kozma Feb 1 '15 at 18:27
  • $\begingroup$ Still, perhaps it would be better to wait for a more sharp estimate. It is interesting to know the asymptotics of $N=N(k)$ such that in every black and white coloring of $N\times N$ square one of the colors contains every $k$-permutation. Not speaking on more colors... $\endgroup$ – Ilya Bogdanov Feb 1 '15 at 19:21
  • $\begingroup$ It seems that the asymptotics of N(k) is sqrt(k) up to polylog-factors, based on the results from "Ordered Ramsey numbers" by David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov. (hint from Martin Balko) arxiv.org/abs/1410.5292 $\endgroup$ – László Kozma Apr 16 '16 at 12:46
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice. Much better than my answer. $\endgroup$ – Tony Huynh Jan 30 '15 at 18:59
  • $\begingroup$ Try the following induction and see where it breaks down: Every coloring of a 2n by 2n square has all k permutations contained by blacks squares and all l permutations contained by white squares, where k+l >= 2n. Gerhard "It Can't Be That Easy?" Paseman, 2015.01.30 $\endgroup$ – Gerhard Paseman Jan 30 '15 at 19:37
  • 1
    $\begingroup$ Very nice - so, together with Ilya Bogdanov's answer the bounds $3n-\epsilon < f(n) \leq n^2$ follow. It seems interesting now to try narrowing the gap. $\endgroup$ – László Kozma Feb 1 '15 at 18:25
  • 2
    $\begingroup$ It seems that the asymptotics of $f(n)$ is $n^2$, up to a polylog factor, based on the results from "Ordered Ramsey numbers" by David Conlon, Jacob Fox, Choongbum Lee, Benny Sudakov. (hint from Martin Balko) arxiv.org/abs/1410.5292 $\endgroup$ – László Kozma Apr 16 '16 at 12:47
  • 1
    $\begingroup$ @LászlóKozma, please do post an answer if you'd like to explain the connection. $\endgroup$ – Ben Barber Apr 17 '16 at 14:25
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.