Description
Abstract: We consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each n≥7�≥7, we construct a planar point set of size (7/8)⋅2n−2(7/8)⋅2�−2 which is saturated for convex n�-gons. That is, the set contains no n� points in convex position while the addition of any new point creates such a configuration. This demonstrates that the saturation number is smaller than the Ramsey number for the Erdős--Szekeres problem. The proof also shows that the original Erdős--Szekeres construction is indeed saturated.
Our construction is based on a similar improvement for the saturation version of the cups-versus-caps theorem. Moreover, we consider the generalization of the cups-versus-caps theorem to monotone paths in ordered hypergraphs. In contrast to the geometric setting, we show that this abstract saturation number is always equal to the corresponding Ramsey number.
Joint work with Zichao Dong, Manfred Scheucher and Ji Zeng.