Suk, Andrew ;
Zeng, Ji
A Positive Fraction ErdősSzekeres Theorem and Its Applications
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 > (k1)², 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 blockmonotone of depth k and blocksize s. Our theorem is asymptotically best possible and follows from a more general Ramseytype 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) blockmonotone subsequences of depth at least k, upon deleting at most (k1)² 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}sSzekeres Theorem and Its Applications}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {62:162:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16070},
URN = {urn:nbn:de:0030drops160703},
doi = {10.4230/LIPIcs.SoCG.2022.62},
annote = {Keywords: Erd\H{o}sSzekeres, blockmonotone, monotone biarc diagrams, mutually avoiding sets}
}
01.06.2022
Keywords: 

ErdősSzekeres, blockmonotone, monotone biarc diagrams, mutually avoiding sets 
Seminar: 

38th International Symposium on Computational Geometry (SoCG 2022)

Issue date: 

2022 
Date of publication: 

01.06.2022 