Three Generalizations of Davenport-Schinzel Sequences
arXiv:1401.5709
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- {\em double DS} sequences, for all , 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 (5)
- Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations
- Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture
- Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
- -quasi planar graphs
- The number of edges in k-quasi-planar graphs