License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagSemProc.08081.4
URN: urn:nbn:de:0030-drops-15291
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1529/
Go to the corresponding Portal

Pettie, Seth

Sources of Superlinearity in Davenport-Schinzel Sequences

pdf-format:
08081.PettieSeth.Paper.1529.pdf (0.5 MB)

Abstract

A {em generalized} Davenport-Schinzel 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 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 {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:DagSemProc.08081.4,
  author =	{Pettie, Seth},
  title =	{{Sources of Superlinearity in Davenport-Schinzel Sequences}},
  booktitle =	{Data Structures},
  pages =	{1--14},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{8081},
  editor =	{Lars Arge and Robert Sedgewick and Raimund Seidel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2008/1529},
  URN =		{urn:nbn:de:0030-drops-15291},
  doi =		{10.4230/DagSemProc.08081.4},
  annote =	{Keywords: Davenport-Schinzel Sequences, lower envelopes, splay trees}
}

Keywords: Davenport-Schinzel Sequences, lower envelopes, splay trees
Collection: 08081 - Data Structures
Issue Date: 2008
Date of publication: 16.06.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI