# Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences

Journal Article (Journal Article)

We obtain sharp upper and lower bounds on the maximal length λ (n) of (n, s)-Davenport-Schinzel sequences, i.e., sequences composed of n symbols, having no two adjacent equal elements and containing no alternating subsequence of length s + 2. We show that (i) λ (n) = Θ(n·2 ); (ii) for s > 4, λ (n) ≤ n·2 if s is even and λ (n) ≤ n·2 if s is odd, where C (n) is a function of α(n) and s, asymptotically smaller than the main term; and finally (iii) for even values of s > 4, λ (n) = Ω(n·2 ), where K = (( (s - 2) 2)!) and Q is a polynomial in α(n) of degree at most (s - 4) 2. © 1989. s 4 s s s s s s s s s s α(n) (α(n)) (s - 2) 2 + C (n) (α(n)) (s - 3) 2 log(α(n)) + C (n) K (α(n)) (s - 2) 2 + Q (n) -1

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Sharir, M; Shor, P

### Published Date

- January 1, 1989

### Published In

### Volume / Issue

- 52 / 2

### Start / End Page

- 228 - 274

### Electronic International Standard Serial Number (EISSN)

- 1096-0899

### International Standard Serial Number (ISSN)

- 0097-3165

### Digital Object Identifier (DOI)

- 10.1016/0097-3165(89)90032-0

### Citation Source

- Scopus