Sharp bounds on Davenport-Schinzel sequences of every order
Seth Pettie · 2013
One of the oldest unresolved problems in extremal combinatorics is to determine the maximum length of Davenport-Schinzel sequences, where an order-s DS sequence is defined to be one over an n-letter alphabet that avoids alternating subsequences of the form a ··· b ··· a ··· b ··· 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 become an indispensable tool in computational geometry and the analysis of discrete geometric structures.