论文标题
在Erdős-tuza-valtr上
On the Erdős-Tuza-Valtr Conjecture
论文作者
论文摘要
Erdős-Szekeres的猜想指出，飞机上的任何超过$ 2^{n-2} $点的集合都包含凸$ n $ -gon的顶点。 Erdős, Tuza, and Valtr strengthened the conjecture by stating that any set of more than $\sum_{i = n - b}^{a - 2} \binom{n - 2}{i}$ 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 曲线。他们还表明，概括实际上等同于ErdősSzekeres的猜想。 我们证明了自1935年Erdős和Szekeres的原始论文以来的Erdős-Tuza-Valtr猜想的第一个新案例。即，我们表明，任何一组$ \ binom {n-1} {2} {2} + 2 $点在一条线上没有三个点，而没有两个点共享相同的$ x $ - 坐标，要么包含4个点，要么包含4个点，要么在凹面曲线上，要么包含4个点，要么包含4个点。
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} \binom{n - 2}{i}$ 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 $\binom{n-1}{2} + 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.
