[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?