Abstract:We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v=a_1a_2...a_m$ of integers such that 1) $1 \leq a_i \leq n$, 2) $a_i=a_j, i\not =j$ implies $|i-j|\geq k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that $$ f(u,n)=O(n2^{O(\alpha (n)^{|u|-4})}). $$ Here $|u|$ is the length of $u$ and $\alpha (n)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which treat the case $u=abababa...$ and is achieved by similar methods.
Keywords: sequence, Davenport-Schinzel sequence, length, upper bound
AMS Subject Classification: 05D99