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 \(\sqrt{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,\dots ,A_k\subset A\), appearing sequentially, all of size \(s=\Omega (n/k^2)\), such that every subsequence \((a_1,\dots ,a_k)\), with \(a_i\in A_i\), is increasing, or every such subsequence is decreasing. The subsequence \(S=(A_1,\dots ,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.
This is a preview of subscription content, log in via an institution to check access.
We’re sorry, something doesn't seem to be working properly.
Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.
References
Aronov, B., Erdős, P., Goddard, W., Kleitman, D.J., Klugerman, M., Pach, J., Schulman, L.J.: Crossing families. In: 7th Annual Symposium on Computational Geometry (North Conway 1991), pp. 351–356. ACM, New York (1991)
Bar Yehuda, R., Fogel, S.: Partitioning a sequence into few monotone subsequences. Acta Inform. 35(5), 421–440 (1998)
Bárány, I., Valtr, P.: A positive fraction Erdős–Szekeres theorem. Discrete Comput. Geom. 19(3), 335–342 (1998)
de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, Berlin (2008)
Bernhart, F., Kainen, P.C.: The book thickness of a graph. J. Combin. Theory Ser. B 27(3), 320–331 (1979)
Di Giacomo, E., Didimo, W., Liotta, G., Wismath, S.K.: Curve-constrained drawings of planar graphs. Comput. Geom. 30(1), 1–23 (2005)
Erdös, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)
Fox, J., Pach, J., Sudakov, B., Suk, A.: Erdős–Szekeres-type theorems for monotone paths and convex bodies. Proc. Lond. Math. Soc. 105(5), 953–982 (2012)
Fredman, M.L.: On computing the length of longest increasing subsequences. Discrete Math. 11(1), 29–35 (1975)
Milans, K.G., Stolee, D., West, D.B.: Ordered Ramsey theory and track representations of graphs. J. Comb. 6(4), 445–456 (2015)
Mirzaei, M., Suk, A.: A positive fraction mutually avoiding sets theorem. Discrete Math. 343(3), # 111730 (2020)
Moshkovitz, G., Shapira, A.: Ramsey theory, integer partitions and a new proof of the Erdős–Szekeres theorem. Adv. Math. 262, 1107–1129 (2014)
Pach, J., Rubin, N., Tardos, G.: Planar point sets determine many pairwise crossing segments. Adv. Math. 386, # 107779 (2021)
Pór, A., Valtr, P.: The partitioned version of the Erdős–Szekeres theorem. Discrete Comput. Geom. 28(4), 625–637 (2002)
Steele, J.M.: Variations on the monotone subsequence theme of Erdős and Szekeres. In: Discrete Probability and Algorithms (Minneapolis 1993). IMA Vol. Math. Appl., vol. 72, pp. 111–131. Springer, New York (1995)
Valtr, P.: On mutually avoiding sets. The Mathematics of Paul Erdős, vol. 2. Algorithms Combin., vol. 14, pp. 324–332. Springer, Berlin (1997)
Acknowledgements
We wish to thank the anonymous SoCG referees for their valuable suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Editor in Charge: Kenneth Clarkson
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
A.S.: supported by NSF CAREER award DMS-1800746, NSF award DMS-1952786, and an Alfred Sloan Fellowship. J.Z.: supported by NSF grant DMS-1800746
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Suk, A., Zeng, J. A Positive Fraction Erdős–Szekeres Theorem and Its Applications. Discrete Comput Geom 71, 308–325 (2024). https://doi.org/10.1007/s00454-023-00510-3
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-023-00510-3