## 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:
Server: fubinf.inf.fu-berlin.de
File:   pub/reports/tr-b-94-04.ps.gz

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