Chromatic variants of the Erdős--Szekeres theorem on points in convex position. (Q1410590)

Let \(S\) be a point set in the plane in general position, that is, no three of the points are collinear. An \(m\)-point subset \(T\) of \(S\) in convex position is called an \(m\)-hole in \(S\) if conv(\(T\)) is a polygon whose interior does not contain any point from \(S\). Let \(S=S_1\dot\cup \dots \cdot\cup S_k\) be a partition of a planar point set \(S\), in general position in the plane. Assume that each set \(S_i\) is non-empty, and refer to it as the set of points of color \(i\). A subset \(T\) of \(S\) is called monochromatic if all its points have the same color, and polychromatic otherwise. The term heterochromatic is used for sets in which every element has a different color. In the paper the authors consider the following set of problems. Given an integer \(m\) and a set \(S\) as above, with possible additional requirements for \(n=| S| \) to be large enough, can one find an \(m\)-hole of \(S\) falling into one of the three described chromatic classes? Or an \(m\)-subset in convex position? Define \(n_M(m, k)\) as the smallest integer with the property that any set of at least this many points, in general position in the plane, colored with \(k\) colors contains a monochromatic \(m\)-subset in convex position. For \(n\geq k\), let \(MC(n, m, k)\) be the largest number of compatible monochromatic \(m\)-holes that can be found in every \(k\)-colored \(n\)-set. In the paper the authors determine or give estimates for these numbers. Moreover, they also examine the heterochromatic and polychromatic variants of these quantities, the numbers \(n_H(m, k)\), \(n_P(m, k)\), \(HC(n, m, k)\), and \(PC(n, m, k)\) which are defined analogously. The organization of the paper is the following. In Section 2 they describe a number of simple observations regarding the functions \(n_M\), \(n_H\), and \(n_P\). Sections 3, 4 , and 5 are devoted to the detailed study of the functions \(MC, HC\), and \(PC\), respectively. Finally, a detailed summary is given in table form at the end of the paper which contains all values determined in the article.