The Happy Ending theorem for planar families of convex bodies

Combinatorics Seminar
Friday, October 4, 2013 - 3:05pm
1 hour (actually 50 minutes)
Skiles 005
École Normale Supérieure
The Erdos-Szekeres (happy ending) theorem claims that among any N points in general position in the plane there are at least log_4(n) of them that are the vertices of a convex polygon. I will explain generalizations of this result that were discovered in the last 30 years involving pseudoline arrangements and families of convex bodies. After surveying some previous work I will present the following results: 1) We improve the upper bound of the analogue Ramsey function for families of disjoint and noncrossing convex bodies. In fact this follows as a corollary of the equivalence between a conjecture of Goodman and Pollack about psudoline arrangements and a conjecture of Bisztrinsky and Fejes Toth about families of disjoint convex bodies. I will say a few words about how we show this equivalence. 2) We confirm a conjecture of Pach and Toth that generalizes the previous result. More precisely we give suffcient and necesary conditions for the existence of the analogue Ramsey function in the more general case in which each pair of bodies share less than k common tangents (for every fixed k). These results are joint work with Andreas Holmsen and Michael Dobbins.