Pettie, Seth
Sources of Superlinearity in DavenportSchinzel Sequences
Abstract
A {em generalized} DavenportSchinzel sequence is one over a finite alphabet
that contains no subsequences isomorphic to a fixed {em 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(n2^{alpha(n)^{O(1)}})$, where $alpha$ is the inverseAckermann 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 {em 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.
BibTeX  Entry
@InProceedings{pettie:DSP:2008:1529,
author = {Seth Pettie},
title = {Sources of Superlinearity in DavenportSchinzel Sequences},
booktitle = {Data Structures},
year = {2008},
editor = {Lars Arge and Robert Sedgewick and Raimund Seidel},
number = {08081},
series = {Dagstuhl Seminar Proceedings},
ISSN = {18624405},
publisher = {Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1529},
annote = {Keywords: DavenportSchinzel Sequences, lower envelopes, splay trees}
}
Keywords: 

DavenportSchinzel Sequences, lower envelopes, splay trees 
Seminar: 

08081  Data Structures

Issue date: 

2008 
Date of publication: 

16.06.2008 