June 16, Wednesday
12:00 – 13:30
Everything you always wanted to know about generalized Davenport-Schinzel sequences* (*but were afraid to ask)
Computer Science seminar
Lecturer : Seth Pettie
Affiliation : Department of EECS,University of Michigan
Location : 202/37
Host : Dr. Michael Elkin
A {it generalized} Davenport-Schinzel sequence is one over a finite
alphabet, none of whose subsequences are isomorphic to some fixed
{it forbidden subsequence}. Davenport-Schinzel sequences have been
used in bounding the complexity of geometric arrangements and the running
time of algorithms and data structures. Let Ex(s,n) be the maximum length
of an s-free sequence over an n-letter alphabet. The foremost open
problem in this area is to characterize the asymptotic growth of Ex(s,n),
for different forbidden subsequences s. In this talk I will survey
everything that is known and worth knowing about the function Ex(s,n),
including some new results