Monotone Subsequences in Any Dimension

✍ Scribed by Ryan Siders

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 147 KB
• Volume: 85
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.1998.2907

✦ Synopsis

We exhibit sequences of n points in d dimensions with no long monotone subsequences, by which we mean when projected in a general direction, our sequence has no monotone subsequences of length -n+d or more. Previous work proved that this function of n would lie betweenn and 2 -n; this paper establishes that the coefficient ofn is one. This resolves the question of how the Erdo s Szekeres result that a (one-dimensional) sequence has monotone subsequences of at most n generalizes to higher dimensions.

1999 Academic Press

With this pattern one could list k 2 numbers with no subsequence longer than k. In the 60 years since this was proven, at least two papers have asked whether this could be generalized to higher dimensions. That is: can