Three Generalizations of Davenport-Schinzel Sequences

2014/01/22 by Seth Pettie, Pettie, Seth · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.DM #graph theory and CDMA systems #math.CO #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1401.5709

arxiv created 2014/01/22 · openalex publication_date 2014/01/22 · arxiv updated 2014/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Cited by

• Bounds for approximating lower envelopes with polynomials of degree at\n most d

Related

• An algorithm for bounding extremal functions of forbidden sequences
• Sharp Bounds on Davenport-Schinzel Sequences of Every Order
• Sources of Superlinearity in Davenport-Schinzel Sequences
• Lower Bounds on Davenport-Schinzel Sequences via Rectangular\n Zarankiewicz Matrices
• Constructing sparse Davenport-Schinzel sequences