Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 05.06.2014 at 12:20 in S6, there is the following noon lecture:

Sharp Bounds on Davenport-Schinzel Sequences of Every Order

Seth Pettie

University of Michigan

Abstract

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 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 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.

An extended abstract was

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010