Open caps and cups in planar point sets (Q2369923): Difference between revisions

Erdős and Szekeres proved their classical result, Theorem 1. For any \(n\geq 3\), there exists a (least) integer \(F(n)\) such that any set of at least \(F(n)\) points in general position in the plane contains \(n\) points in convex position, by showing that for any \(k,\ell\geq 2\) there is a (least) integer \(F'(k,\ell)\) such that any configuration of at least \(F'(k,\ell)\) points contains a \(k\)-cap or an \(\ell\)-cup. Here a configuration \(P\) is a finite set of points in general position in the plane such that no two points have the same \(x\)-coordinate; and a \(k\)-cap (resp. \(k\)-cup) is a sequence of \(k\) points \(p_1,\dots, p_k\) with increasing \(x\)-coordinates that are the vertices of a convex \(k\)-gon with all points \(p_2,\dots, p_{k-1}\) lying above (resp. below) the segment \(p_1p_k\). Here the author investigates the related problem of open caps and cups, i.e. caps and cups with no points of the configuration vertically above, resp. below, the polygonal arc \(p_1,\dots, p_k\). He gives double exponential bounds for the minimal size of \(P\).