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}_{1}{a}_{2}...{a}_{m}$ of integers such that 1) $1\le {a}_{i}\le n$, 2) ${a}_{i}={a}_{j},i\ne j$ implies $|i-j|\ge 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\left(n{2}^{O\left(\alpha {\left(n\right)}^{\left|u\right|-4}\right)}\right).$$
Here $\left|u\right|$ is the length of $u$ and $\alpha \left(n\right)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which...