The partitioned version of the Erdős-Szekeres theorem
type: Item
instance of: scholarly article
title: The partitioned version of the Erdős-Szekeres theorem
zbMATH Open document ID: 1019.52011
author: Attila Pór
author: Pavel Valtr
published in: Discrete \& Computational Geometry
publication date: 2003-03-17T00:00:00Z
review text: For \(k\geq 4\), a finite planar point set \(X\) is called a convex \(k\)-clustering if it is a disjoint union of \(k\) sets \(X_1, \ldots , X_k\) of equal sizes such that \(x_1x_2\ldots x_k\) is a convex \(k\)-gon for each choice of \(x_1\in X_1,\ldots , x_k\in X_k\). The authors answer a question of Gil Kalai: they show that for every \(k\geq 4\) there are two constants \(c=c(k)\), \(c'=c'(k)\) such that the following holds. If \(X\) is a finite set of points in general position in the plane, then it has a subset \(X'\) of size at most \(c'\) such that \(X/X'\) can be partitioned into at most \(c\) convex \(k\)-clusterings. The special case \(k=4\) was proved earlier by Pór. Their result strengthens the so-called positive fraction Erdős-Szekeres theorem proved by Bárány and Valtr. The proof gives reasonable estimates on \(c\) and \(c'\), and it works also in higher dimensions. The authors also improve the previous constants for the positive fraction Erdős-Szekeres theorem obtained by Pach and Solymosi.
reviewed by: Ferenc Fodor
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 1883347
zbMATH Keywords: Erdős-Szekeres theorem
zbMATH Keywords: \(k\)-clustering
zbMATH Keywords: points in convex position
zbMATH Keywords: positive fraction Erdős-Szekeres theorem
MaRDI profile type: Publication
full work available at URL: s00454-002-2894-1
OpenAlex ID: W2093184634
DOI: 10.1007/S00454-002-2894-1
description: scientific article; zbMATH DE number 1883347