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\prec 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. \par 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 alternate graphs contain no $k$-path is well quasiordered by that containment.
Keywords: : Davenport-Schinzel sequence, extremal problem, linear growth, minimal obstacle to linearity, well quasiordering, alternate graph
AMS Subject Classification: 05D99, 06A07