We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Positive Fraction Erdős–Szekeres Theorem and Its Applications.
- Authors
Suk, Andrew; Zeng, Ji
- 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) 2 , 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 2) , 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 2 log k) 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.
- Subjects
REAL numbers; POINT set theory; RAMSEY theory
- Publication
Discrete & Computational Geometry, 2024, Vol 71, Issue 1, p308
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-023-00510-3