### DIMACS and Rutgers Discrete Mathematics Seminar

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

Speaker: **Seth Pettie, University of Michigan**, Seth Pettie, University of Michigan

Date: Monday, October 27, 2014 3:30-4:30pm

Location: Hill Center, Room 705, Rutgers University, Busch Campus, Piscataway, NJ

A Davenport-Schinzel sequence with order s is a sequence over an n-letter alphabet that avoids alternating 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 discrete geometry and the analysis of algorithms.
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 when s is
odd, DS_s behaves essentially like the preceding DS_{s-1}. The
results refute both common sense and a conjecture of Alon, Kaplan,
Nivasch, Sharir, and Smorodinsky [2008]. Prior to this work, sharp
upper and lower bounds were only known for s up to 3 and even s>3.
The full manuscript is available at arXiv:1204.1086. An extended
abstract was presented at the 2013 Symposium on Computational
Geometry.