Dmitriy Zakharov: Convex polytopes from fewer points

Description of video

Date: 9/16/22
Speaker :Zakharov Dmitry

Let ESd(n) denote the smallest integer such that any set of ESd(n) points in Rd in general position contains n points in convex position. In 1960, Erdős and Szekeres showed that ES2(n)2n2+1 holds, and famously conjectured that their construction is optimal. This was nearly settled by Suk in 2017, who showed that ES2(n)2n+o(n). We show that ESd(n)=2o(n)holds for all d3. Joint work with Cosmin Pohoata.

Downloads

Related videos

Lower bounds for incidences

Zakharov Dmitrii

BBC+G Seminar

on 4/5/24

Dániel Simon Saturated Partial Embeddings of Maximal Planar Graphs

Dániel Simon Saturated Partial Embeddings of Maxim Dániel Simon Saturated Partial Embeddings of Maxim

BBC+G Seminar

on 11/29/24