Saturation results around the Erdős--Szekeres problem
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908578389950464 |
|---|---|
| author | Damásdi, Gábor Dong, Zichao Scheucher, Manfred Zeng, Ji |
| author_facet | Damásdi, Gábor Dong, Zichao Scheucher, Manfred Zeng, Ji |
| contents | In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_01223 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Saturation results around the Erdős--Szekeres problem Damásdi, Gábor Dong, Zichao Scheucher, Manfred Zeng, Ji Combinatorics In this paper, we consider saturation problems related to the celebrated Erdős--Szekeres convex polygon problem. For each $n \ge 7$, we construct a planar point set of size $(7/8) \cdot 2^{n-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. |
| title | Saturation results around the Erdős--Szekeres problem |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2312.01223 |