Sharp Bounds on Davenport-Schinzel Sequences of Every Order – University of Copenhagen

Sharp Bounds on Davenport-Schinzel Sequences of Every Order

Talk by Seth Pettie, Associate Professor University of Michigan


A Davenport-Schinzel sequence with order s is a sequence over an n-letter alphabet that avoids subsequences of the form a..b..a..b.. with length s+2.  They were originally used to bound the complexity of the lower envelope of degree-s polynomials or any class of functions that cross at most s times.  They have numerous applications in computational geometry.

Let λs(n) be the maximum length of such a sequence.  In this talk I'll present a new method for obtaining sharp bounds on λs(n) for every order s.  This work reveals the unexpected fact that sequences with odd order s behave essentially like even order s-1.

The results refute both common sense and a conjecture of Alon, Kaplan, Nivasch, Sharir, and Smorodinsky [2008].  Prior to this work, tight upper and lower bounds
were only known for s up to 3 and even s>3.


Seth Pettie is a professor of computer science at the University of Michigan, Ann Arbor.  He received his Ph.D. in 2003 from the University of Texas at Austin and was an Alexander von Humboldt postdoctoral fellow at the Max Planck Institute for Computer Science in Saarbruecken, Germany.