2022/06/09 by Baek, Jineon
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2206.04260
The Erdős-Szekeres conjecture states that any set of more than 2n-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 ∑i = n - ba - 2 \binomn - 2i 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 \binomn-12 + 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.