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