We define $ STR(n)$ to be the longest sequence of strings with $ n$ symbols such that the $ k$ th string has at most k symbols, the symbols of the string are taken from an alphabet consisting of $ n$ characters, and no string is a sub-string of a previous one.

For example, $ STR(1)=1$ , because the longest sequence is “a”. $ STR(2)=3$ , because the longest sequence is “a”, “bb”, “b”. I’m not sure how big $ STR(3)$ is.

We do know, however, that $ STR(n)$ is always finite, for the same reason that $ TREE(n)$ and $ SSCG(n)$ (see well-quasi-order).

My question, what is the growth rate of $ STR$ ? It is slower than $ TREE$ , since strings can embed in trees.

(In particular, if we could find $ n$ such that $ STR(n)>TREE(3)$ , that would be great.)