Combinatorial aspects of Davenport-Schinzel sequences Original Research Article

A finite sequence u = a1a2 … ap of some symbols is contained in another sequence v = b1b2 … bq if there is a subsequence bi1, bi2 … bip of v which can be identified, after an injective renaming of symbols, with u. We say that u = a1a2 … ap is k-regular if i - j ⩾ k whenever ai = aj, 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 Ph.D. 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.