 License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-160703
URL:

;

### A Positive Fraction Erdős-Szekeres Theorem and Its Applications

 pdf-format:

### Abstract

A famous theorem of Erdős and Szekeres states that any sequence of n distinct real numbers contains a monotone subsequence of length at least √n. Here, we prove a positive fraction version of this theorem. For n > (k-1)², any sequence A of n distinct real numbers contains a collection of subsets A_1,…, A_k ⊂ A, appearing sequentially, all of size s = Ω(n/k²), such that every subsequence (a_1,…, a_k), with a_i ∈ A_i, is increasing, or every such subsequence is decreasing. The subsequence S = (A_1,…, A_k) described above is called block-monotone of depth k and block-size s. Our theorem is asymptotically best possible and follows from a more general Ramsey-type result for monotone paths, which we find of independent interest. We also show that for any positive integer k, any finite sequence of distinct real numbers can be partitioned into O(k²log k) block-monotone subsequences of depth at least k, upon deleting at most (k-1)² entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.

### BibTeX - Entry

```@InProceedings{suk_et_al:LIPIcs.SoCG.2022.62,
author =	{Suk, Andrew and Zeng, Ji},
title =	{{A Positive Fraction Erd\H{o}s-Szekeres Theorem and Its Applications}},
booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
pages =	{62:1--62:15},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-227-3},
ISSN =	{1868-8969},
year =	{2022},
volume =	{224},
editor =	{Goaoc, Xavier and Kerber, Michael},
publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
DROPS-Home | Fulltext Search | Imprint | Privacy 