Almost linear upper bounds on the length of general davenport—schinzel sequences

Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We obtain almost linear upper bounds on the length λ_s(n) of Davenport—Schinzel sequences composed ofn symbols in which no alternating subsequence is of length greater thans+1. These bounds are of the formO(nα(n)^O(α(n)5-3)), and they generalize and extend the tight bound Θ(nα(n)) obtained by Hart and Sharir for the special cases=3 (α(n) is the functional inverse of Ackermann’s function), and also improve the upper boundO(n log*n) due to Szemerédi. Work on this paper has been supported in part by a grant from the U.S. — Israeli Binational Science Foundation.