March 6th, Wednesday 14:15, Room 303, Jacobs Building

Title: Tight Bounds on Davenport-Schinzel Sequences of Every Order

Lecturer: Seth Pettie

Lecturer homepage : http://web.eecs.umich.edu/~pettie/

Affiliation : Department of EECS, University of Michigan

 

A Davenport-Schinzel 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 DS_s(n) be the maximum length of such a sequence. In this talk I'll present a new method for obtaining tight bounds on DS_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, refuting 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 all even s>3 [Davenport-Schinzel 1965, Hart-Sharir 1984, Agarwal-Sharir-Shor 1987, Klazar 1999, Nivasch 2009].