KAIST Discrete Math Seminar

In 1935 Erdős and Szekeres showed that every “sufficiently large” set of points in general position in the plane contains a “large” subset which is in convex position. Since then many mathematicians have tried to determine good bounds for “sufficiently large” in  terms of “large”, as well as given numerous generalizations and refinements. In this talk I will survey this famous problem and extend it to a natural object which we call generalized wiring diagram. This unifies several proposed generalizations, and as a result we will settle several conjectures in this area. This is joint work with Michael Dobbins and Alfredo Hubard.