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 |