On the Erd\H{o}s-Tuza-Valtr Conjecture

arXiv2206.04260MaRDI QIDQ6401537FDOQ6401537

Authors: Jineon Baek 

Publication date: 9 June 2022

Abstract: The ErdH{o}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. ErdH{o}s, Tuza, and Valtr strengthened the conjecture by stating that any set of more than $$ 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 ErdH{o}s-Szekeres conjecture. We prove the first new case of the ErdH{o}s-Tuza-Valtr conjecture since the original 1935 paper of ErdH{o}s and Szekeres. Namely, we show that any set of $$ 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.

This page was built for publication: On the Erd\H{o}s-Tuza-Valtr Conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6401537)