Mathematics Department - Discrete Math - Fall 2014

Discrete Math - Fall 2014


Jeffry Kahn, Hao Huang


Upcoming Talks

Monday, October 27th

Special Discrete Math

Seth Pettie, University of Michigan

"Sharp Bounds on Davenport-Schinzel Sequences of Every Order"

Time: 3:30 PM
Location: Hill 705
Abstract: 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.  

This page was last updated on August 29, 2014 at 01:59 pm and is maintained by
For questions regarding courses and/or special permission, please contact
For questions or comments about this site, please contact
© 2014 Rutgers, The State University of New Jersey. All rights reserved.