Generalized Davenport-Schinzel Sequences

Pavel Valtr (joint work with Martin Klazar) Department of Applied Mathematics Charles University Czech Republic email: valtr@CSPGUK11.bitnet Report B 94-04 January 94

Get the report here or by anonymous ftp: 
File:   pub/reports/
The extremal function $Ex(u,n)$ (introduced in the theory of Davenport-Schinzel sequences in other notation) denotes for a fixed finite alternating sequence $u=ababa\ldots$ the maximum length of a finite sequence $v$ over $n$ symbols with no immediate repetition which does not contain $u$. Here (following the idea of J. Ne\v set\v ril) we generalize this concept for arbitrary sequence $u$. We summarize the already known properties of $Ex(u,n)$ and we present also two new theorems which give good upper bounds on $Ex(u,n)$ for $u$ consisting of (two) smaller subsequences $u_i$ provided we have good upper bounds on $Ex(u_i,n)$. We use these theorems to describe a wide class of sequences $u$ ("linear sequences") for which $Ex(u,n)=O(n)$. Both theorems are used for obtaining new superlinear upper bounds as well. We partially characterize linear sequences over three symbols. We also present several problems about $Ex(u,n)$.\\[2mm] {\bf Key words:}\ Davenport-Schinzel sequence, extremal problem, maximum length