Monotone subsets in lattices and the Schensted shape of a Sós permutation

Abstract

For a fixed irrational number $\alpha$ and $n\in \mathbb{N}$, we look at the shape of the sequence $(f(1),\dots ,f(n))$ after Schensted insertion, where $f(i)=\alpha i\mathrm{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.

arXiv comment36 pages, 8 figures