Metadata only

Date

2012-06Type

- Conference Paper

ETH Bibliography

yes
Altmetrics

Abstract

Let P=(p1,p2,...,pN) be a sequence of points in the plane, where pi=(xi,yi) and x1<x2...xN. A famous 1935 Erdos-Szekeres theorem asserts that every such P contains a monotone subsequence S of √N points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of Ω(log 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 ⊆ 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 ⊆ 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 Ω(log(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(log log 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 R3, as well as for a Ramsey-type theorem for hyperplanes in R4 recently used by Dujmovic and Langerman. Show more

Publication status

publishedExternal links

Book title

SoCG '12: Proceedings of the Twenty-Eighth Annual Symposium on Computational GeometryPages / Article No.

Publisher

Association for Computing MachineryEvent

Subject

Combinatorial geometry; Erdös-Szekeres theorem; Ramsey theory; Order typeOrganisational unit

03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)
More

Show all metadata
ETH Bibliography

yes
Altmetrics