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^-3 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 (1s).