Extremal functions for sequences

AbstractDavenport-Schinzel sequences DS(s) are finite sequences of some symbols with no immediate repetition and with no alternating subsequence (i.e. of the type ababab …) of the length s. This concept based on a geometrical motivation is due to Davenport and Schinzel in the middle of 1960s. In the late 1980s strong lower and upper (superlinear) bounds on the maximum length of the DS(s) sequences on n symbols were found. DS(s) sequences are well known to computer geometrists because of their application to the estimates of the complexity of the lower envelopes.Here we summarize some properties of the generalization of this concept and prove that the extremal functions of aa… abb… baa… abb… b grow linearly