Extremal functions for sequences

✍ Scribed by Martin Klazar

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 390 KB
• Volume: 150
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(95)00188-3

✦ Synopsis

Davenport-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.

1. Introduction, motivation and notation

We will consider finite sequences u,v,w .... consisting of arbitrary symbols a, b, c .... and we will consider Extremal Theory of such sequences defined as follows.