A general upper bound in extremal theory of sequences

@article{Klazar1992,
abstract = {We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v=a_1a_2...a_m$ of integers such that 1) $1 \le a_i \le n$, 2) $a_i=a_j, i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that \[ f(u,n)=O(n2^\{O(\alpha (n)^\{|u|-4\})\}). \] Here $|u|$ is the length of $u$ and $\alpha (n)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which treat the case $u=abababa\ldots $ and is achieved by similar methods.},
author = {Klazar, Martin},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {sequence; Davenport-Schinzel sequence; length; upper bound; extremal theory; Davenport-Schinzel sequences; upper bound; maximal length},
language = {eng},
number = {4},
pages = {737-746},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {A general upper bound in extremal theory of sequences},
url = {http://eudml.org/doc/247383},
volume = {33},
year = {1992},
}

TY - JOUR
AU - Klazar, Martin
TI - A general upper bound in extremal theory of sequences
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1992
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 33
IS - 4
SP - 737
EP - 746
AB - We investigate the extremal function $f(u,n)$ which, for a given finite sequence $u$ over $k$ symbols, is defined as the maximum length $m$ of a sequence $v=a_1a_2...a_m$ of integers such that 1) $1 \le a_i \le n$, 2) $a_i=a_j, i\ne j$ implies $|i-j|\ge k$ and 3) $v$ contains no subsequence of the type $u$. We prove that $f(u,n)$ is very near to be linear in $n$ for any fixed $u$ of length greater than 4, namely that \[ f(u,n)=O(n2^{O(\alpha (n)^{|u|-4})}). \] Here $|u|$ is the length of $u$ and $\alpha (n)$ is the inverse to the Ackermann function and goes to infinity very slowly. This result extends the estimates in [S] and [ASS] which treat the case $u=abababa\ldots $ and is achieved by similar methods.
LA - eng
KW - sequence; Davenport-Schinzel sequence; length; upper bound; extremal theory; Davenport-Schinzel sequences; upper bound; maximal length
UR - http://eudml.org/doc/247383
ER -