A positive fraction Erdős-Szekeres theorem (Q1387842)

The Erdős-Szekeres theorem says that among sufficiently many points in general position in the plane one can always find \(k\) points in convex position, that means they are the vertices of a convex \(k\)-gon. The authors prove the following fractional version of this theorem. For every integer \(k\geq 4\) there is a constant \(c_k>0\) with the following property. Every sufficiently large finite set \(X\subset \mathbb{R}^2\) in general position contains \(k\) subsets \(Y_1,\ldots ,Y_k\), each of size \(\geq c_k| X| \), such that every transversal of the \(Y_i\) is in convex position. (A transversal of the \(Y_i\) is a set \(\{y_1,\ldots ,y_k\}\) with \(y_i\in Y_i\).) The main tool is a lemma stating that any finite set \(X\subset \mathbb{R}^d\) contains ``large'' subsets \(Y_1,\ldots ,Y_k\) such that all transversals of the \(Y_i\) have the same order type. (Two \(k\)-tuples \((x_1,\ldots ,x_k)\) and \((y_1,\ldots ,y_k)\) are said to have the same order type if the orientations of the simplices \(x_{i_1}\cdots x_{i_{d+1}}\) and \(y_{i_1}\cdots y_{i_{d+1}}\) are the same for every \(1\leq i_1<\ldots <i_{d+1}\leq k\).) Some related results are also proved, for instance a positive fraction Tverberg theorem.