Sharp Upper and Lower Bounds on the Length of General Davenport-Schinzel Sequences

We obtain sharp upper and lower bounds on the maximal length lambda sub s (n) of (n,s)-Davenport-Schinzel sequences, i.e. sequences composed of n symbols, having no two adjacent equal elements, and containing no alternating subsequences of lengths+2. We show that (i)lambda sub 4(n)=THETA(n.2 sup alpha (n)),(ii) for s > 4, lambda sub s (n) 4, lambda sub s (n) = OMEGA (n.2 sup K(s)(alpha(n)) s-2 over 2 +Q(s)(n))) where K sub s = 1 over (s-2) over 2 ! and Qs is a polynomial in alpha(n) of degree at most s-4 over 2.