Seminar Event Detail

Student Combinatorics

Date:  Monday, January 31, 2022
Location:  3866 East Hall (4:00 PM to 5:00 PM)

Title:  On the Erdos-Tuza-Valtr Conjecture

Abstract:   The infamous Erdos-Szekeres Conjecture states that the number of points on a plane in general position with no n (greater than 1) points in convex position, called an n-gon, is at most 2^(n-2).
They later provided a construction S_n of exactly that many points avoiding any such n-gon.

Erdos, Tuza and Valtr discovered that, if the conjecture is true, the 'interval' subset S_{n, a, b} of the maximal construction S_n should also attain the maximum size while avoiding any n-gon, a-cap or b-cup for a, b <= n <= a + b - 4.
Here, an m-cap (or m-cup) is a point set of size m that can be connected by a graph of some concave (or convex) function.
Indeed, an abstract set-theoretic generalization by Peters and Szekeres was disproved by Balko and Valtr by showing that the set S_{n, n, 4} is not maximal in this set-theoretic setting.

In this work, we show the optimality of S_{n, n, 4} in the original geometric setting.
That is, (n-2) choose 2 + 2 points in a general position either determine a 4-cap or n-gon.

It shows for the first time the optimality of a nontrivial subset of S_n not covered by the Erdos-Szekeres theorem on caps and cups.
The proof also generalizes to a set-theoretic setup slightly different from that of Peters and Szekeres, suggesting that the full conjecture may generalize in the same way.


Speaker:  Jin Baek
Institution:  UM

Event Organizer:     


Edit this event (login required).
Add new event (login required).
For access requests and instructions, contact

Back to previous page
Back to UM Math seminars/events page.