Math @ Duke

Publications [#235559] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M; Shor, P, Sharp upper and lower bounds on the length of general DavenportSchinzel sequences,
Journal of Combinatorial Theory, Series A, vol. 52 no. 2
(1989),
pp. 228274, ISSN 00973165
(last updated on 2018/06/24)
Abstract: We obtain sharp upper and lower bounds on the maximal length λs(n) of (n, s)DavenportSchinzel 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) λ4(n) = Θ(n·2α(n)); (ii) for s > 4, λs(n) ≤ n·2(α(n)) (s  2) 2 + Cs(n) if s is even and λs(n) ≤ n·2(α(n)) (s  3) 2log(α(n)) + Cs(n) if s is odd, where Cs(n) is a function of α(n) and s, asymptotically smaller than the main term; and finally (iii) for even values of s > 4, λs(n) = Ω(n·2Ks(α(n)) (s  2) 2 + Qs(n)), where Ks = (( (s  2) 2)!)1 and Qs is a polynomial in α(n) of degree at most (s  4) 2. © 1989.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

