Abstract:

A finite sequence u=a_1a_2... a_p of some symbols is contained in another sequence v=b_1b_2... b_q if there is a subsequence b_{i_1}b_{i_2}... b_{i_p} of v which can be identified, after an injective renaming of symbols, with u. We say that u=a_1a_2... a_p is k-regular if i-j>= k whenever a_i=a_j, i>j. We denote further by |u| the length p of u and by ||u|| the number of different symbols in u. In this expository paper we give a survey of combinatorial results concerning the containment relation. Many of them are from the author's PhD thesis with the same title. Extremal results concern the growth rate of the function Ex(u,n)=max |v|, the maximum is taken over all ||u||-regular sequences v, ||v||<= n, not containing u. This is a generalization of the case u=ababa... which leads to Davenport-Schinzel sequences. Enumerative results deal with the numbers of abab-free and abba-free sequences. We mention a well quasiordering result and a tree generalization of our extremal function from sequences (=colored paths) to colored trees.