Computer Science – Discrete Mathematics
Scientific paper
2007-07-11
Computer Science
Discrete Mathematics
Scientific paper
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(\sigma,n) be the maximum length of a sequence over an alphabet of size n avoiding subsequences isomorphic to \sigma. It has been proved that for every \sigma, Ex(\sigma,n) is either linear or very close to linear; in particular it is O(n 2^{\alpha(n)^{O(1)}}), where \alpha is the inverse-Ackermann function and O(1) depends on \sigma. However, very little is known about the properties of \sigma that induce superlinearity of \Ex(\sigma,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.
No associations
LandOfFree
Sources of Superlinearity in Davenport-Schinzel Sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Sources of Superlinearity in Davenport-Schinzel Sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sources of Superlinearity in Davenport-Schinzel Sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-160739