Erdős-Szekeres for (not so) Restricted Point Sets

We consider a variant of the famous Erdős-Szekeres problem for point sets with bounded diameter. For a set of \(n\) points in general position in \(R^d\), we define the diameter \(\Delta(P)\) to be the ratio \(max\{d(a,b)\} / min\{d(a,b)\}\), where both the maximum and minimum are over all pairs a and b from \(P\). Previously, such problems were considered only in the extremal case, when \(\Delta(P) = O(n^{1/d})\); these point sets are often called dense. It is known that every dense point set in \(R^d\) contains a subset of \(\Omega(n^{(d-1)/(d+1)})\) in convex position, and that this is sharp. Note that this guarantees the existence of a polynomially-sized convex subset. On the other hand, if no restriction is imposed on the diameter, it is known that sometimes the maximal size of such subsets is only logarithmic in \(n\). We prove that for every \(\tau \in [1/d,1)\), there is an \(\varepsilon(\tau) > 0\) such that any set \(P\) of n points in \(R^d\) in general position with \(\Delta(P) = O(n^\tau)\) contains a subset of \(\Omega(n^{\varepsilon(\tau)})\) points in convex position. This generalizes the results of Valtr [Discrete and Computational Geometry, 1992], Dumitrescu and Tóth [unpublished, 2022], and Bukh and Dong [Advances in Combinatorics, 2025].

This is joint work with Todor Antić, Martin Balko, Koki Furukawa, and Pavel Valtr.