Date: Monday, January 31, 2022
Location: 3866 East Hall (4:00 PM to 5:00 PM)
Title: On the ErdosTuzaValtr Conjecture
Abstract: The infamous ErdosSzekeres 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 ngon, is at most 2^(n2).
They later provided a construction S_n of exactly that many points avoiding any such ngon.
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 ngon, acap or bcup for a, b <= n <= a + b  4.
Here, an mcap (or mcup) is a point set of size m that can be connected by a graph of some concave (or convex) function.
Indeed, an abstract settheoretic 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 settheoretic setting.
In this work, we show the optimality of S_{n, n, 4} in the original geometric setting.
That is, (n2) choose 2 + 2 points in a general position either determine a 4cap or ngon.
It shows for the first time the optimality of a nontrivial subset of S_n not covered by the ErdosSzekeres theorem on caps and cups.
The proof also generalizes to a settheoretic setup slightly different from that of Peters and Szekeres, suggesting that the full conjecture may generalize in the same way.
Files:
Speaker: Jin Baek
Institution: UM
Event Organizer:
