Return to Colloquia & Seminar listing

### On the Erdos-Tuza-Valtr Conjecture

**Algebra & Discrete Mathematics**

Speaker: | Jineon Baek, University of Michigan |

Related Webpage: | https://lsa.umich.edu/math/people/phd-students/jineon.html |

Location: | 2112 MSB |

Start time: | Fri, May 13 2022, 12:10PM |

Erdos, Tuza and Valtr conjectured that any set of more than $\sum_{i = n + 2 - b}^{a} \binom{n - 2}{i - 2}$ points in a plane with no three on a line 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. This conjecture strengthens the famous conjecture of Erdos and Szekeres that any set of more than $2^{n-2}$ points with no three on a line contains the vertices of a convex $n$-gon. We prove the first new case of the Erdos-Tuza-Valtr conjecture since the original Erdos-Szekeres paper. Namely, we show that any set of $\binom{n-2}{2} + 2$ points in the plane with no three points on a line either contains a 4-cap or the vertices of a convex $n$-gon.