Abstract:

In the first part of the paper we are concerned about finite sequences (over arbitrary symbols) u for which Ex(u,n)=O(n). The function Ex(u,n) measures the maximum length of finite sequences over n symbols which contain no subsequence of the type u. It follows from the result of Hart and Sharir that the containment ababa<u is a (minimal) obstacle to Ex(u,n)=O(n). We show by means of a construction due to Sharir and Wiernik that there is another obstacle to the linear growth.

In the second part of the paper we investigate whether the above containment of sequences is wqo. It is trivial that it is not but we show that the smaller family of sequences whose alternace graphs contain no k-path is well quasiordered by that containment.