Combinatorial Theory

For a fixed irrational number \(\alpha\) and \(n\in \mathbb{N}\), we look at the shape of the sequence \((f(1),\ldots,f(n))\) after Schensted insertion, where \(f(i) = \alpha i \mod 1\). Our primary result is that the boundary of the Schensted shape is approximated by a piecewise linear function with at most two slopes. This piecewise linear function is explicitly described in terms of the continued fraction expansion for \(\alpha\). Our results generalize those of Boyd and Steele, who studied longest monotone subsequences. Our proofs are based on a careful analysis of monotone sets in two-dimensional lattices.

Mathematics Subject Classifications: 05A05, 11H06, 11B57, 11K06

Keywords: Longest increasing subsequence, Schensted shape, geometry of numbers, S os permutations