Erdos-Szekeres-type theorems for monotone paths and convex bodies

Fox, Jacob; Pach, Janos; Sudakov, Benny; Suk, Andrew

doi:10.1112/plms/pds018

research article

Erdos-Szekeres-type theorems for monotone paths and convex bodies

Fox, Jacob

•

Pach, Janos

•

Sudakov, Benny

2012

Proceedings Of The London Mathematical Society

For any sequence of positive integers j(1)< j(2)

= 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.