Publication Date:
2012-11-11
Description:
For any sequence of positive integers j 1 〈 j 2 〈···〈 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 and . Determining the other values of these functions appears to be a difficult task. Here we show that 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 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.
Print ISSN:
0024-6115
Electronic ISSN:
1460-244X
Topics:
Mathematics
Permalink
