MIT-Harvard-MSR Combinatorics Seminar

Speaker:  Dmitrii Zakharov (MIT)

Title:  Convex polytopes from fewer points

Abstract:

Let ES_d(n) denote the smallest integer such that any set of ES_d(n) points in R^d in general position contains n points in convex position. In 1960, Erdős and Szekeres showed that ES_2(n)≥2^{n−2}+1 holds, and famously conjectured that their construction is optimal. This was nearly settled by Suk in 2017, who showed that ES_2(n)≤2^{n+o(n)}. We show that ES_d(n)=2^{o(n)} holds for all d≥3. Joint work with Cosmin Pohoata.