The Erdos-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.
Later, Erdos, Tuza and Valtr strengthened the conjecture by stating that any set of more than \sum_{i = n + 2 - b}^{a} \binom{n - 2}{i - 2} points in a plane 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.
They also showed that the generalization is actually equivalent to the Erdos-Szekeres conjecture.
We prove the first new case of the Erdos-Tuza-Valtr conjecture since the original 1935 paper of Erdos and Szekeres.
Namely, we show that any set of (n-1)(n-2)/2 + 2 points in the plane with no three points on a line and no two points sharing the same x-coordinate either contains a 4-cap or the vertices of a convex n-gon. Speaker(s): Jineon Baek (University of Michigan)
Later, Erdos, Tuza and Valtr strengthened the conjecture by stating that any set of more than \sum_{i = n + 2 - b}^{a} \binom{n - 2}{i - 2} points in a plane 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.
They also showed that the generalization is actually equivalent to the Erdos-Szekeres conjecture.
We prove the first new case of the Erdos-Tuza-Valtr conjecture since the original 1935 paper of Erdos and Szekeres.
Namely, we show that any set of (n-1)(n-2)/2 + 2 points in the plane with no three points on a line and no two points sharing the same x-coordinate either contains a 4-cap or the vertices of a convex n-gon. Speaker(s): Jineon Baek (University of Michigan)
| Building: | East Hall |
|---|---|
| Event Type: | Workshop / Seminar |
| Tags: | Mathematics |
| Source: | Happening @ Michigan from Department of Mathematics, Combinatorics Seminar - Department of Mathematics |
