Title:

Generalized Davenport-Schinzel Sequences: Regaining Linearity

Abstract:

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.