Aarhus University Seal / Aarhus Universitets segl

MADALGO Seminar

MADALGO theory seminar, Bryan Wilkinson, MADALGO

Info about event

Time

Wednesday 3 September 2014,  at 14:15 - 15:00

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.