Higher-order Erdos--Szekeres theorems

Understand

Let P=(p_1,p_2,...,p_N) be a sequence of points in the plane, where p_i=(x_i,y_i) and x_1<x_2<...<x_N.

• A famous 1935 Erdos--Szekeres theorem asserts that every such P contains a monotone subsequence S of $\sqrt N$ points.
• Another, equally famous theorem from the same paper implies that every such P contains a convex or concave subsequence of $\Omega(\log N)$ points.
• Monotonicity is a property determined by pairs of points, and convexity concerns triples of points.