Three Generalizations of Davenport-Schinzel Sequences

Abstract

We present new, and mostly sharp, bounds on the maximum length of certain generalizations of Davenport-Schinzel sequences. Among the results are sharp bounds on order-$s$ {\em double DS} sequences, for all $s$, sharp bounds on sequences avoiding {\em catenated permutations} (aka formation free sequences), and new lower bounds on sequences avoiding {\em zig-zagging} patterns.

References in corpus (1)

• Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture

Cited by in corpus (2)

• Bounding extremal functions of forbidden $0-1$ matrices using $(r,s)$-formations
• Bounds for approximating lower envelopes with polynomials of degree at most $d$