A positive fraction Erdős-Szekeres theorem and its applications

DOI10.1007/S00454-023-00510-3MaRDI QIDQ6186490zbMATH OpenOpenAlexWikidataFDO

Authors Andrew Suk, Ji Zeng

Publication date 9 January 2024

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.01750

zbMATH Keywords

Biarc diagramsblock-monotone sequencesErdős-Szekeres theoremmutually avoiding sets

Mathematics Subject Classification ID

Combinatorial aspects of finite geometries (05B25) Graph representations (geometric and intersection representations, etc.) (05C62) Extremal combinatorics (05D99)

Abstract: A famous theorem of Erdos and Szekeres states that any sequence of $n$ distinct real numbers contains a monotone subsequence of length at least $sqrtn$. Here, we prove a positive fraction version of this theorem. For $n>(k-1{)}^2$, any sequence $A$ of $n$ distinct real numbers contains a collection of subsets $A_1,ldots,A_{k}subsetA$, appearing sequentially, all of size $s=Omega(n/k^2)$, such that every subsequence $(a_1,ldots,a_k)$, with $a_{i}in{A}_i$, is increasing, or every such subsequence is decreasing. The subsequence $S=(A_1,ldots,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^{2}logk)$ block-monotone subsequences of depth at least $k$, upon deleting at most $(k-1{)}^2$ entries. We apply our results to mutually avoiding planar point sets and biarc diagrams in graph drawing.

Recommendations

• A positive fraction Erdős-Szekeres theorem and its applications
• Higher-order Erdős-Szekeres theorems
• Higher-order Erdős-Szekeres theorems
• On the number of monotone sequences
• Erdős-Szekeres theorem for multidimensional arrays

Cites work

• A positive fraction Erdős-Szekeres theorem
• A positive fraction mutually avoiding sets theorem
• Computational geometry. Algorithms and applications.
• Crossing families
• Curve-constrained drawings of planar graphs
• Erdős-Szekeres-type theorems for monotone paths and convex bodies
• scientific article; zbMATH DE number 795114 (Why is no real title available?)
• scientific article; zbMATH DE number 970816 (Why is no real title available?)
• scientific article; zbMATH DE number 3019031 (Why is no real title available?)
• On computing the length of longest increasing subsequences
• Ordered Ramsey theory and track representations of graphs
• Partitioning a sequence into few monotone subsequences
• Ramsey theory, integer partitions and a new proof of the Erdős-Szekeres theorem
• The book thickness of a graph
• The partitioned version of the Erdős-Szekeres theorem

Cited in

(2)

• A positive fraction Erdős-Szekeres theorem and its applications
• A canonical tree decomposition for order types, and some applications

This page was built for publication: A positive fraction Erdős-Szekeres theorem and its applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6186490)