Ramsey numbers and monotone colorings

Abstract

For positive integers $N$ and $r\ge 2$, an $r$-monotone coloring of $\left(\genfrac{}{}{0ex}{}{\{1,\dots ,N\}}{r}\right)$ is a 2-coloring by $-1$ and $+1$ that is monotone on the lexicographically ordered sequence of $r$-tuples of every $(r+1)$-tuple from~$\left(\genfrac{}{}{0ex}{}{\{1,\dots ,N\}}{r+1}\right)$. Let ${\overline{R}}_{mon}(n;r)$ be the minimum $N$ such that every $r$-monotone coloring of $\left(\genfrac{}{}{0ex}{}{\{1,\dots ,N\}}{r}\right)$ contains a monochromatic copy of $\left(\genfrac{}{}{0ex}{}{\{1,\dots ,n\}}{r}\right)$. For every $r\ge 3$, it is known that ${\overline{R}}_{mon}(n;r)\le to{w}_{r-1}(O(n))$, where $to{w}_h(x)$ is the tower function of height $h-1$ defined as $to{w}_1(x)=x$ and $to{w}_h(x)=2^{to{w}_{h-1}(x)}$ for $h\ge 2$. The Erdős--Szekeres Lemma and the Erdős--Szekeres Theorem imply ${\overline{R}}_{mon}(n;2)=(n-1{)}^2+1$ and ${\overline{R}}_{mon}(n;3)=\left(\genfrac{}{}{0ex}{}{2n-4}{n-2}\right)+1$, respectively. It follows from a result of Eliáš and Matoušek that ${\overline{R}}_{mon}(n;4)\ge to{w}_3(\Omega (n))$. We show that ${\overline{R}}_{mon}(n;r)\ge to{w}_{r-1}(\Omega (n))$ for every $r\ge 3$. This, in particular, solves an open problem posed by Eliáš and Matoušek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating ${\overline{R}}_{mon}(n;r)$ and two Ramsey-type problems that have been recently considered by several researchers. Namely, we show connections with higher-order Erdős--Szekeres theorems and with Ramsey-type problems for order-type homogeneous sequences of points. We also prove that the number of $r$-monotone colorings of $\left(\genfrac{}{}{0ex}{}{\{1,\dots ,N\}}{r}\right)$ is $2^{N^{r-1}/r^{\Theta (r)}}$ for $N\ge r\ge 3$, which generalizes the well-known fact that the number of simple arrangements of~$N$ pseudolines is $2^{\Theta (N^2)}$.

20 pages, 6 figures