On the Erdős-Tuza-Valtr Conjecture

Abstract

The Erdős-Szekeres conjecture states that any set of more than $2^{n-2}$ points in the plane with no three on a line contains the vertices of a convex $n$-gon. Erdős, Tuza, and Valtr strengthened the conjecture by stating that any set of more than ${\sum }_{i=n-b}^{a-2}\left(\genfrac{}{}{0ex}{}{n-2}{i}\right)$ points in a plane either contains the vertices of a convex $n$-gon, $a$ points lying on a concave downward curve, or $b$ points lying on a concave upward curve. They also showed that the generalization is actually equivalent to the Erdős-Szekeres conjecture. We prove the first new case of the Erdős-Tuza-Valtr conjecture since the original 1935 paper of Erdős and Szekeres. Namely, we show that any set of $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)+2$ points in the plane with no three points on a line and no two points sharing the same $x$-coordinate either contains 4 points lying on a concave downward curve or the vertices of a convex $n$-gon.

16 pages, 8 figures