Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2407.20641 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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(\infty,k)$, is well-studied, known for $f(\infty,3)$ and $f(\infty,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 \ge 3$, the gap between $f(s,k)$ and $f(\infty,k)$ is $Θ(\frac{1}{s})$.