Let $w$ be a word over the alphabet $[n] := \{1, \dots, n\}$. For a fixed $S \subseteq [n]$, let $w_S$ be the word obtained from $w$ by deleting all entries not in $S$, then removing (all but one instance of) consecutive duplicate letters. We say $w$ is $k$-permutation-avoiding (for some fixed $k \in \mathbb N$) if for any $S \subseteq [n]$ with $|S| = k$, $w_S$ does not contain a contiguous subword of length $k$ whose letters are all different (in other words, $w_S$ does not contain a permutation of $S$ as a factor).
For example, the word $14742142562324215$ is not $5$-permutation-avoiding, since putting $S = \{3, 4, 5, 6, 7\}$, $w_S = 47456345$ which contains the permutation $74563$ as a factor. The word $16564656365646562$, however, is $5$- (and in fact even $4$-)permutation avoiding.
Let $\mu(n, k)$ be the minimum length of a $k$-permutation-avoiding word over $[n]$ in which all $n$ letters appear. I am interested in the asymptotics of $\mu(n, k)$. I would especially love to know if something like this has been studied before, or if you know of any potentially useful results in this direction; I am not an expert in combinatorics on words, so I am not sure whether I am googling the right things.
What we know so far:
- $\mu(n, 3) = \infty$ for all $n \geq 3$ (it is impossible to avoid a $3$-permutation);
- $\mu(n, 4)$ is exponential in $n$. Indeed, the construction of $4$-permutation-avoiding word in the example above can be generalised to produce an upper bound; a lower bound is a bit (but not too much) more involved;
- In general, for fixed $k$, $\mu(n, k)$ is superpolynomial in $n$, but the proof of that (if correct) is surprisingly complicated, and the constants involved are potentially terrible (think tower of exponentials of height $k$).
