Sharp Bounds on Davenport-Schinzel Sequences of Every Order

Abstract

One of the longest-standing open problems in computational geometry is to bound the lower envelope of \(n\) univariate functions, each pair of which crosses at most \(s\) times, for some fixed \(s\). This problem is known to be equivalent to bounding the length of an order-\(s\) Davenport-Schinzel sequence, namely a sequence over an \(n\)-letter alphabet that avoids alternating subsequences of the form \(a \cdots b \cdots a \cdots b \cdots\) with length \(s+2\). These sequences were introduced by Davenport and Schinzel in 1965 to model a certain problem in differential equations and have since been applied to bounding the running times of geometric algorithms, data structures, and the combinatorial complexity of geometric arrangements. Let \(\lambda_s(n)\) be the maximum length of an order-\(s\) DS sequence over \(n\) letters. What is \(\lambda_s\) asymptotically? This question has been answered satisfactorily (by Hart and Sharir, Agarwal, Sharir, and Shor, Klazar, and Nivasch) when \(s\) is even or \(s\le 3\). However, since the work of Agarwal, Sharir, and Shor in the mid-1980s there has been a persistent gap in our understanding of the odd orders. In this work we effectively close the problem by establishing sharp bounds on Davenport-Schinzel sequences of every order \(s\). Our results reveal that, contrary to one's intuition, \(\lambda_s(n)\) behaves essentially like \(\lambda_{s-1}(n)\) when \(s\) is odd. This refutes conjectures due to Alon et al. (2008) and Nivasch (2010).