Fox, JacobPach, JanosSudakov, BennySuk, Andrew2013-02-272013-02-272013-02-27201210.1112/plms/pds018https://infoscience.epfl.ch/handle/20.500.14299/89288WOS:000311305100003For any sequence of positive integers j(1)< j(2)<center dot center dot center dot < j(n), the k-tuples (j(i), j(i+1), ..., j(i+k-1)), i=1, 2, ..., n-k+1, are said to form a monotone path of length n. Given any integers n >= k >= 2 and q >= 2, what is the smallest integer N with the property that no matter how we color all k-element subsets of [N]={1, 2, ..., N} with q colors, we can always find a monochromatic monotone path of length n? Denoting this minimum by N-k(q, n), it follows from the seminal paper of Erdos and Szekeres in 1935 that N-2(q, n)=(n-1)(q)+1 a N-3(2,n) = ((2n-4)(n-2)) +1. Determining the other values of these functions appears to be a difficult task. Here we show that 2((n/q)q-1) <= N-3(q,n) <= 2(nq-1) (log n), for q >= 2 and n >= q+2. Using a 'stepping-up' approach that goes back to Erdos and Hajnal, we prove analogous bounds on N-k(q, n) for larger values of k, which are towers of height k-1 in n(q-1). As a geometric application, we prove the following extension of the Happy Ending Theorem. Every family of at least M (n) = 2(log n)(n2) plane convex bodies in general position, any pair of which share at most two boundary points, has n members in convex position, that is, it has n members such that each of them contributes a point to the boundary of the convex hull of their union.text::journal::journal article::research article