On the positive fraction Erdős-Szekeres theorem for convex sets
type: Item
instance of: scholarly article
title: On the positive fraction Erdős-Szekeres theorem for convex sets
zbMATH Open document ID: 1107.52012
author: Attila Pór
author: Pavel Valtr
published in: European Journal of Combinatorics
publication date: 2006-11-15T00:00:00Z
review text: The authors improve a result of \textit{J. Pach} and \textit{J. Solymosi} [Discrete Comput. Geom. 19, No. 3, 427--435 (1998; Zbl 0905.52001)] on the ``Positive Fraction Erdős-Szekeres Theorem for convex bodies'', where a convex body is taken to mean a convex and compact set in the plane. The result states that for any \(k\geq3\), there is an \(\varepsilon_k>0\) such that any finite family~\(X=\{X_1,\dots,X_n\}\) of disjoint convex bodies ``in general position'' contains a \(k\)-cluster of size at least \(\lfloor\varepsilon_k\cdot n\rfloor\). Here, a \(k\)-cluster \((k\geq4)\) is a family \(\mathcal F=\{\mathcal F_1,\dots,\mathcal F_k\}\) of \(k\) disjoint subfamilies of convex bodies with the following two properties: The~\(\mathcal F_i\) must all have the same cardinality, and each transversal \(\{F_1,\dots,F_k\}\) with \(F_i\in\mathcal F_i\) must be in convex position, meaning that no \(F_i\) lies in the convex hull of the others. The authors improve Pach and Solymosi's bound of \(\varepsilon_k \in 2^{-O(k^2)}\) to \(\varepsilon_k\in 2^{-37.8k-o(1)}\). It is known that \(\varepsilon_k<2^{-k+o(1)}\) [see \textit{A. Pór} and \textit{P. Valtr}, Discrete Comput. Geom. 28, No. 4, 625--637 (2002; Zbl 1019.52011)].
reviewed by: Julian Pfeifle
Mathematics Subject Classification ID: 52C10
zbMATH DE Number: 5072921
MaRDI profile type: Publication
full work available at URL: j.ejc.2006.06.015
OpenAlex ID: W4210739075
cites work: A positive fraction Erdős-Szekeres theorem
cites work: A generalization of the Erdös-Szekeres convex n-gon theorem.
cites work: Convexly independent sets
cites work: Q5759552
cites work: Canonical theorems for convex sets
cites work: A generalisation of the Erdős-Szekeres theorem to disjoint convex sets
cites work: The partitioned version of the Erdős-Szekeres theorem
DOI: 10.1016/J.EJC.2006.06.015
description: scientific article; zbMATH DE number 5072921