Saturation Results Around the Erdős–Szekeres Problem

Damásdi, Gábor and Dong, Zichao and Scheucher, Manfred and Zeng, Ji (2024) Saturation Results Around the Erdős–Szekeres Problem. Leibniz International Proceedings in Informatics (LIPIcs) . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Schloss Dagstuhl.

Preview

Text 2312.01223v2.pdf - Draft Version Download (727kB) | Preview

Abstract

In this paper, we consider saturation problems related to the celebrated Erdős–Szekeres convex polygon problem. For each n ≥ 7, we construct a planar point set of size (7/8) · 2n−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.

Actions (login required)

Edit Item