[home] / [math] / Erdős-Szekeres Conjecture

The Erdős-Szekeres Conjecture (and its dual)

Plot of the points on axis \((x, y)\) and the dual lines on the axis \((m, b)\):

\[ \newcommand{\conv}{\mathop{\rm conv}\nolimits}\]

Let \(P = \{p_1, p_2, \ldots, p_n\}\) be a set of points. We define the convex hull of \(P\) as \[ \conv P = \{\sum \lambda_i p_i : \sum_{i=1}^{n} \lambda_i = 1 \text{ and } \lambda_i \geq 0 \text{ for all } i\}\] A set of points \(P\) is said to be in the convex position if for all \(p \in P\), \(p \not\in \conv (P\setminus \{p\})\).

Given a point \(p = (x_0, y_0)\), there is a unique line which passes through \(p\) with slope \(m\). Using the slope-intercept form, \(mx+b=y\), we have \(b(m) = y_0 - x_0 m\). The points above are in green, and the lines are in blue. A set of \(n\) points will produce \(n\) lines in this manner. What characterizes a set of lines which corresponds to a set in the convex position?