Higher-order Erdős-Szekeres theorems

DOI10.1016/J.AIM.2013.04.020zbMATH Open1283.05175arXiv1111.3824OpenAlexW2404118392MaRDI QIDQ2437401FDOQ2437401

Authors: Marek Eliáš, Jiří Matoušek 

Publication date: 3 March 2014

Published in: Advances in Mathematics (Search for Journal in Brave)

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 $sqrtN$ points. Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of $Omega(logN)$ 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 $KsubseteqP$ 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 $SsubseteqP$ 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(lo{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(loglogN)$ 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.

Full work available at URL: https://arxiv.org/abs/1111.3824

Recommendations

• Higher-order Erdős-Szekeres theorems
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Monotone subsequences in any dimension
• On the number of monotone sequences
• Ramsey numbers and monotone colorings

zbMATH Keywords

Ramsey theoryhypergraphdivided differenceorder type\(k\)th-order monotone subsetErdős-Szekeres theorem

Mathematics Subject Classification ID

Paths and cycles (05C38) Generalized Ramsey theory (05C55) Erd?s problems and related topics of discrete geometry (52C10) Ramsey theory (05D10)

Cites Work

• Interpolation and approximation by polynomials
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial Theorems on Classifications of Subsets of a Given Set
• The Erdos-Szekeres problem on points in convex position – a survey
• Title not available (Why is that?)
• Title not available (Why is that?)
• An improved bound for the stepping-up lemma
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• Good splitters for counting points in triangles
• A center transversal theorem for hyperplanes and applications to graph drawing
• Higher-order Erdős-Szekeres theorems
• Ramsey-type results for semi-algebraic relations

Cited In (27)

• Ramsey numbers for degree monotone paths
• Ramsey numbers and monotone colorings
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• A note on the Erdős-Szekeres theorem in two dimensions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Connectivity of triangulation flip graphs in the plane
• Higher order Utiyama-like theorem
• Title not available (Why is that?)
• Lexicographic Ramsey theory
• The Erdős-Hajnal hypergraph Ramsey problem
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• Curves in \(\mathbb R^d\) intersecting every hyperplane at most \(d+1\) times
• Erdős-Szekeres-type statements: Ramsey function and decidability in dimension 1
• Higher order Turán inequalities for combinatorial sequences
• Ramsey numbers of ordered graphs
• On the number of monotone sequences
• Erdős-Szekeres type theorems for ordered uniform matchings
• Ordered unavoidable sub-structures in matchings and random matchings
• Erdős-Szekeres tableaux
• Title not available (Why is that?)
• The saturation number for the length of degree monotone paths
• Higher-order Erdős-Szekeres theorems
• Three-monotone interpolation
• A note on order-type homogeneous point sets
• Semi-algebraic Ramsey numbers
• Ramsey numbers of ordered graphs

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)