Abstract:

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 sharp 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.  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 all even s>3.

A manuscript is available at arXiv:1204.1086 <http://arxiv.org/pdf/1204.1086v2.pdf>.  An extended abstract appeared in the Symposium on Computational Geometry.

Host: Gerth Stølting Brodal