Combinatorial aspects of Davenport-Schinzel sequences

✍ Scribed by Martin Klazar

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 994 KB
• Volume: 165-166
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/s0012-365x(96)00189-6

✦ Synopsis

A finite sequence u = ala2 . up of some symbols is contained in another sequence c = h1b2.. b, if there is a subsequence b,,bi, b,, of u which can be identified, after an injective renaming of symbols, with u. We say that u = u1a2.. .up is k-regular if i -j > k whenever a, = a,, i > j. We denote further by (~1 the length p of u and by lluli 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 It'l, the maximum is taken over all Ilu)(-regular sequences II, (/L'/( <n, not containing U. This is a generalization of the case u = abubu which leads to Davenport-Schinzel sequences. Enumerative results deal with the numbers of ubab-free and ubba-free sequences. We mention a well-quasiordering result and a tree generalization of our extremal function from sequences (= colored paths) to colored trees.