Erdős-Szekeres theorem for point sets with forbidden subconfigurations
type: Item
instance of: scholarly article
title: Erdős-Szekeres theorem for point sets with forbidden subconfigurations
zbMATH Open document ID: 1253.52006
author: Gyula Károlyi
author: Géza Tóth
published in: Discrete \& Computational Geometry
publication date: 2012-09-19T00:00:00Z
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.
reviewed by: László A. Székely
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 6084045
zbMATH Keywords: order type
zbMATH Keywords: Erdős-Szekeres theorem
zbMATH Keywords: combinatorial convexity
MaRDI profile type: Publication
full work available at URL: s00454-012-9424-6
OpenAlex ID: W2030260203
cites work: Enumerating order types for small point sets with applications
cites work: Ramsey-type theorems with forbidden subgraphs
cites work: Crossing families
cites work: Q4547794
cites work: A positive fraction Erdős-Szekeres theorem
cites work: The Erdős-Hajnal conjecture for bull-free graphs
cites work: A decomposition theorem for partially ordered sets
cites work: Ramsey-type theorems
cites work: Q3286826
cites work: Induced Ramsey-type theorems
cites work: Q3138746
cites work: Sets with No Empty Convex 7-Gons
cites work: A new proof of the Erdős-Szekeres convex k-gon result
cites work: Erdős--Szekeres theorem with forbidden order types
cites work: Point configurations in \(d\)-space without large subsets in convex position
cites work: The Erdos-Szekeres problem on points in convex position – a survey
cites work: A Ramsey property of order types
cites work: The partitioned version of the Erdős-Szekeres theorem
cites work: Q5290279
DOI: 10.1007/S00454-012-9424-6
description: scientific article; zbMATH DE number 6084045