2007/07/11 by Seth Pettie, Pettie, Seth
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.0707.1715
arxiv created 2007/07/11 · openalex publication_date 2007/07/11 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A generalized Davenport-Schinzel sequence is one over a finite alphabet that contains no subsequences isomorphic to a fixed forbidden subsequence. One of the fundamental problems in this area is bounding (asymptotically) the maximum length of such sequences. Following Klazar, let Ex(σ,n) be the maximum length of a sequence over an alphabet of size n avoiding subsequences isomorphic to σ. It has been proved that for every σ, Ex(σ,n) is either linear or very close to linear; in particular it is O(n 2^α(n)O(1)), where αis the inverse-Ackermann function and O(1) depends on σ. However, very little is known about the properties of σthat induce superlinearity of \Ex(σ,n). In this paper we exhibit an infinite family of independent superlinear forbidden subsequences. To be specific, we show that there are 17 prototypical superlinear forbidden subsequences, some of which can be made arbitrarily long through a simple padding operation. Perhaps the most novel part of our constructions is a new succinct code for representing superlinear forbidden subsequences.