Erdős-Szekeres theorem for point sets with forbidden subconfigurations (Q452006): Difference between revisions

According to the Erdős-Szekeres theorem, \(4^n\) points in the plane in general position contain some \(n\) points in convex position. How many points will imply the existence of \(n\) points among them in convex position, if we have an extra condition, namely that a certain (fixed) order type does not occur in the point set? The paper classifies the answer for order types of at least 4 vertices, whose convex hull is a triangle. The answer allows 3 possibilities for growth in \(n\): linear, between a quadratic and a higher polynomial function, and exponential.