Mathematics Colloquia and Seminars

Erdos, Tuza and Valtr conjectured that any set of more than $\sum_{i = n + 2 - b}^{a} \binom{n - 2}{i - 2}$ points in a plane with no three on a line either contains the vertices of a convex $n$-gon, $a$ points lying on an upwardly convex curve, or $b$ points lying on a downwardly convex curve. This conjecture strengthens the famous conjecture of Erdos and Szekeres that any set of more than $2^{n-2}$ points with no three on a line contains the vertices of a convex $n$-gon. We prove the first new case of the Erdos-Tuza-Valtr conjecture since the original Erdos-Szekeres paper. Namely, we show that any set of $\binom{n-2}{2} + 2$ points in the plane with no three points on a line either contains a 4-cap or the vertices of a convex $n$-gon.