Abstract
We explore a question related to the celebrated Erdős-Szekeres Theorem and develop a geometric approach to answer it. Our main object of study is the Erdős-Szekeres Tableau, or EST, of a number sequence. An EST is the sequence of integral points whose coordinates record the length of the longest increasing and longest decreasing subsequence ending at each element of the sequence. We define the Order Poset of an EST in order to answer the question: What information about the sequence can be recovered by its EST?
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Eliáš, M., Matoušek, J.: Higher-order Erdős-Szekeres theorems. In: Symposium on Computational Geometry (2012). Available online at arXiv:1111.3824v3 [cs.CG]
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, 953–982 (2012)
Myers, J.S.: The minimum number of monotone subsequences. Electr. J. Comb. 9(2), 205–224 (2002)
Seidenberg, A.: A simple proof of a theorem of Erdős and Szekeres. J. London Math. Soc. 34, 352 (1959)
Steele, J.M.: Variations on the monotone subsequence theme of Erdős and Szekeres. IMA Vol. Math. Appl. 72, 111–131 (1995)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ault, S.V., Shemmer, B. Erdős-Szekeres Tableaux. Order 31, 391–402 (2014). https://doi.org/10.1007/s11083-013-9308-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11083-013-9308-2