On the positive fraction Erdős-Szekeres theorem for convex sets
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)].
scientific article; zbMATH DE number 5072921