Ramsey numbers and monotone colorings

For positive integers N and r >= 2, an r-monotone coloring of ((r) ({1,...,N})) 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 ((r+1) ({1,...,N})). Let (R) over bar (mon) (n; r) be the minimum N such that every r-monotone coloring of ( (r) ({1,...,N})) contains a monochromatic copy of ((r) ({1,...,n})). For every r >= 3, it is known that (R) over bar (mon) (n; r) <= tow(r-1)(O(n)), where tow(h)(x) is the tower function of height h - 1 defined as tow(1)(x) = x and tow(h)(x) = 2(towh-1(x)) for h >= 2. The Erdos-Szekeres Lemma and the Erdos-Szekeres Theorem imply (R) over bar (mon)(n; 2) = (n - 1)(2) + 1 and (R) over bar (mon)(n ; 3) = ( (n-2) (2n-4) ) + 1, respectively. It follows from a result of Elias and Matousek that (R) over bar (mon)(n; 4) >= tow(3)(Omega(n)). We show that (R) over bar (mon)(n; r) >= tow(r-1)(Omega(n)) for every r >= 3. This, in particular, solves an open problem posed by Elias and Matousek and by Moshkovitz and Shapira. Using two geometric interpretations of monotone colorings, we show connections between estimating (R) over bar (mon)(n;r) and two Ramseytype problems that have been recently considered by several researchers. Namely, we show connections with higher-order Erdos-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})(r )) is 2(Nr-1/r circle minus(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). (C) 2018 Elsevier Inc. All rights reserved.