| | |
| | |
Stat |
Members: 3643 Articles: 2'488'730 Articles rated: 2609
29 March 2024 |
|
| | | |
|
Article overview
| |
|
Higher-order Erdos--Szekeres theorems | Marek Elias
; Jiri Matousek
; | Date: |
16 Nov 2011 | 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 $sqrt N$
points. Another, equally famous theorem from the same paper implies that every
such P contains a convex or concave subsequence of $Omega(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 $Ksubseteq 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 $Ssubseteq 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 $Omega(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(loglog 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. | Source: | arXiv, 1111.3824 | Services: | Forum | Review | PDF | Favorites |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
| News, job offers and information for researchers and scientists:
| |