Erdős-Szekeres-type theorems for monotone paths and convex bodies

For any sequence of positive integers j1<j2<···<jn, the k-tuples (ji, ji+1, …, ji+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 Nk(q, n), it follows from the seminal paper of Erdős and Szekeres in 1935 that N2(q, n)=(n−1)q+1 and N 3 ( 2 , n ) = ( 2 n − 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 n q − 1 log n , for q⩾2 and n⩾q+2. Using a ‘stepping-up’ approach that goes back to Erdős and Hajnal, we prove analogous bounds on Nk(q, n) for larger values of k, which are towers of height k−1 in nq−1. As a geometric application, we prove the following extension of the Happy Ending Theorem. Every family of at least M ( n ) = 2 n 2 log n 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.