Damásdi, Gábor and Dong, Zichao and Scheucher, Manfred and Zeng, Ji (2024) Saturation results around the Erdős-Szekeres problem. In: 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics, LIPIcs (293). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, Wadern, No.-46. ISBN 9783959773164
|
Text
LIPIcs.SoCG.2024.46.pdf - Published Version Available under License Creative Commons Attribution. Download (755kB) | 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.
| Item Type: | Book Section |
|---|---|
| Additional Information: | HUN-REN Alfréd Rényi Institute of Mathematics, Budapest, Hungary ELTE Eötvös Loránd University, Budapest, Hungary Extremal Combinatorics and Probability Group (ECOPRO), Institute for Basic Science (IBS), Daejeon, South Korea Institut für Mathematik, Technische Universität Berlin, Germany University of California, La Jolla, San Diego, CA, United States Conference code: 199976 Export Date: 28 August 2024 Correspondence Address: Damásdi, G.; HUN-REN Alfréd Rényi Institute of MathematicsHungary Correspondence Address: Dong, Z.; HUN-REN Alfréd Rényi Institute of MathematicsHungary Correspondence Address: Scheucher, M.; Institut für Mathematik, Germany Correspondence Address: Zeng, J.; HUN-REN Alfréd Rényi Institute of MathematicsHungary Funding details: European Research Council, ERC, 882971 Funding details: Institute for Basic Science, IBS, IBS-R029-C4 Funding details: Deutsche Forschungsgemeinschaft, DFG, SCHE 2214/1-1 Funding details: National Science Foundation, NSF, DMS-1800746 Funding text 1: G\\u00E1bor Dam\\u00E1sdi: Research partially supported by ERC grant No. 882971, \\u201CGeoScape\\u201D. Zichao Dong: Research supported by ERC grant No. 882971, \\u201CGeoScape\\u201D, by the Erd\\u0151s Center, and by the Institute for Basic Science (IBS-R029-C4). Manfred Scheucher: Supported by DFG grant SCHE 2214/1-1. Ji Zeng: Research supported by NSF grant DMS-1800746, ERC grant No. 882971, \\u201CGeoScape\\u201D, and by the Erd\\u0151s Center. |
| Uncontrolled Keywords: | Convex polygon, Cups-versus-caps, Monotone path, Saturation problem |
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 12 Sep 2025 13:48 |
| Last Modified: | 12 Sep 2025 13:48 |
| URI: | https://real.mtak.hu/id/eprint/224107 |
Actions (login required)
 |
Edit Item |
