A general upper bound in extremal theory of sequences

Klazar, Martin

Commentationes Mathematicae Universitatis Carolinae, Tome 33 (1992) no. 4, pp. 737-746.

Résumé

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 \leq a_i \leq n$, 2) $a_i=a_j, i\not =j$ implies $|i-j|\geq 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.

Détail

Classification : 05D99, 68R15
Keywords: sequence; Davenport-Schinzel sequence; length; upper bound