Generalized Davenport-Schinzel Sequences: Regaining Linearity

Bryan Wilkinson

Aarhus University, Danmark

Aarhus University, Danmark

2014/11/18 Tuesday 4PM-5PM

Room 1409

Room 1409

We prove the linearity (of the lengths) of some generalized Davenport-Schinzel sequences. Standard Davenport-Schinzel sequences of order 2 (avoiding abab) are linear, while those of order 3 (avoiding ababa) and higher can be superlinear. Our goal is to determine what pattern(s), in addition to ababa, must be forbidden to regain linearity. This work is motivated by an intriguing open problem: does the lower envelope of any set of degree 3 polynomials have linear complexity?