On the minimum density of monotone subwords
The electronic journal of combinatorics, Tome 32 (2025) no. 1
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 $\Theta(\frac{1}{s})$.
@article{10_37236_13478,
author = {Raphael Yuster},
title = {On the minimum density of monotone subwords},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {1},
doi = {10.37236/13478},
zbl = {8036399},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13478/}
}
Raphael Yuster. On the minimum density of monotone subwords. The electronic journal of combinatorics, Tome 32 (2025) no. 1. doi: 10.37236/13478
Cité par Sources :