Abstract
For positive integers N and r >= 2, an r-monotone coloring of ({1,...,N} choose r) 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 ({1,...,N} choose r+1). Let R(n;r) be the minimum N such that every r-monotone coloring of ({1,...,N} choose r) contains a monochromatic copy of ({1,...,n} choose r).
For every r >= 3, it is known that R(n;r) = 2. The Erdős-Szekeres Lemma and the Erdős-Szekeres Theorem imply R(n;2) = (n-1)^2+1 and R(n;3) = (2n-4 choose n-2) + 1, respectively.
It follows from a result of Eliáš and Matoušek that R(n;4) >= tow_3(Omega(n)). We show that R(n;r) >= tow_(r-1)(Omega(n)) for every r >= 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 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 ({1,...,N} choose r) is 2^(N^(r-1)/r^(Theta(r))) for N >= r >= 3, which generalizes the well-known fact that the number of simple arrangements of N pseudolines is 2^(Theta(N^2)).