Higher-order Erdős-Szekeres theorems

Abstract: Let P=(p_1,p_2,...,p_N) be a sequence of points in the plane, where p_i=(x_i,y_i) and x_1<x_2<...<x_N. A famous 1935 Erdos--Szekeres theorem asserts that every such P contains a monotone subsequence S of

s q r t N

points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of

O m e g a (l o g N)

points. Monotonicity is a property determined by pairs of points, and convexity concerns triples of points. We propose a generalization making both of these theorems members of an infinite family of Ramsey-type results. First we define a (k+1)-tuple

K s u b s e t e q P

to be positive if it lies on the graph of a function whose kth derivative is everywhere nonnegative, and similarly for a negative (k+1)-tuple. Then we say that

S s u b s e t e q P

is kth-order monotone if its (k+1)-tuples are all positive or all negative. We investigate quantitative bound for the corresponding Ramsey-type result (i.e., how large kth-order monotone subsequence can be guaranteed in every N-point P). We obtain an

O m e g a (l o g^{(k - 1)} N)

lower bound ((k-1)-times iterated logarithm). This is based on a quantitative Ramsey-type theorem for what we call transitive colorings of the complete (k+1)-uniform hypergraph; it also provides a unified view of the two classical Erdos--Szekeres results mentioned above. For k=3, we construct a geometric example providing an

O (l o g l o g N)

upper bound, tight up to a multiplicative constant. As a consequence, we obtain similar upper bounds for a Ramsey-type theorem for order-type homogeneous subsets in R^3, as well as for a Ramsey-type theorem for hyperplanes in R^4 recently used by Dujmovic and Langerman.

Recommendations

Cites work

Cited in

(29)

This page was built for publication: Higher-order Erdős-Szekeres theorems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437401)