Erdős-Szekeres theorem for point sets with forbidden subconfigurations

DOI10.1007/S00454-012-9424-6MaRDI QIDQ452006zbMATH OpenOpenAlexFDO

Authors Gyula Károlyi, Géza Tóth

Publication date 19 September 2012

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00454-012-9424-6

zbMATH Keywords

combinatorial convexityErdős-Szekeres theoremorder type

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

Review text

According to the Erdős-Szekeres theorem, \(4^n\) points in the plane in general position contain some \(n\) points in convex position. How many points will imply the existence of \(n\) points among them in convex position, if we have an extra condition, namely that a certain (fixed) order type does not occur in the point set? The paper classifies the answer for order types of at least 4 vertices, whose convex hull is a triangle. The answer allows 3 possibilities for growth in \(n\): linear, between a quadratic and a higher polynomial function, and exponential.

Recommendations

• Erdős--Szekeres theorem with forbidden order types
• Erdős-Szekeres theorems for families of convex sets
• Erdős-Szekeres theorem for lines
• scientific article; zbMATH DE number 2068096
• scientific article; zbMATH DE number 1786502

Cites work

• A decomposition theorem for partially ordered sets
• A new proof of the Erdős-Szekeres convex k-gon result
• A positive fraction Erdős-Szekeres theorem
• A Ramsey property of order types
• Crossing families
• Enumerating order types for small point sets with applications
• Erdős--Szekeres theorem with forbidden order types
• scientific article; zbMATH DE number 431988 (Why is no real title available?)
• scientific article; zbMATH DE number 3168302 (Why is no real title available?)
• scientific article; zbMATH DE number 1786502 (Why is no real title available?)
• scientific article; zbMATH DE number 5019923 (Why is no real title available?)
• Induced Ramsey-type theorems
• Point configurations in \(d\)-space without large subsets in convex position
• Ramsey-type theorems
• Ramsey-type theorems with forbidden subgraphs
• Sets with No Empty Convex 7-Gons
• The Erdos-Szekeres problem on points in convex position – a survey
• The Erdős-Hajnal conjecture for bull-free graphs
• The partitioned version of the Erdős-Szekeres theorem

Cited in

(10)

• Point configurations in \(d\)-space without large subsets in convex position
• Erdős--Szekeres theorem with forbidden order types
• scientific article; zbMATH DE number 999569 (Why is no real title available?)
• Forbidden k‐Sets in the Plane
• Extremal and probabilistic results for order types
• Convex hulls of random order types
• New bounds for the same-type lemma
• On some extremal results for order types
• More Turán-type theorems for triangles in convex point sets
• Erdős-Szekeres theorem for lines

This page was built for publication: Erdős-Szekeres theorem for point sets with forbidden subconfigurations

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