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<= a_i <=n, 2) a_i=a_j,  i differs from j, implies |i-j|>=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.

Remark:

[S]=M. Sharir, Almost linear upper bounds on the length of generalized Davenport-Schinzel sequences, Combinatorica 7 (1987), 131-143.
[ASS]=P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences, J. Comb. Th. A 52 (1989), 228-274.