On the minimum density of monotone subwords

We consider the asymptotic minimum density $f(s,k)$ of monotone k-subwords of words over a totally ordered alphabet of size s. The unrestricted alphabet case, f(∞,k), is well-studied, known for f(∞,3) and f(∞,4), and, in particular, conjectured to be rational for all k. Here we determine $f(2,k)$ for all k and determine $f(3,3)$, which is already irrational. We describe an explicit construction for all s which is conjectured to yield $f(s,3)$. Using our construction and flag algebra, we determine $f(4,3),f(5,3),f(6,3)$ up to 10⁻³ yet argue that flag algebra, regardless of computational power, cannot determine $f(5,3)$ precisely. Finally, we prove that for every fixed k ≥ 3, the gap between $f(s,k)$ and f(∞,k) is Θ(1/s).