MADALGO Seminar

MADALGO theory seminar, Bryan Wilkinson, MADALGO

2014.09.02 | Trine Ji Holmgaard Jensen

Date Wed 03 Sep
Time 14:15 15:00
Location

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.