Three Generalizations of Davenport-Schinzel Sequences
classification
🧮 math.CO
cs.DM
keywords
sequencesboundssharpavoidingdavenport-schinzelgeneralizationscatenatedcertain
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.