A generalization of the extremal function of the Davenport-Schinzel sequences

Kok Bin Wong, Cheng Yeaw Ku

Published 2013-11-07Version 1

Let $[n]=\{1, \ldots, n\}$. A sequence $u=a_1a_2\dots a_l$ over $[n]$ is called $k$-sparse if $a_i = a_j$, $i > j$ implies $i-j\geq k$. In other words, every consecutive subsequence of $u$ of length at most $k$ does not have letters in common. Let $u,v$ be two sequences. We say that $u$ is $v$-free, if $u$ does not contain a subsequence isomorphic to $v$. Suppose there are only $k$ letters appearing in $v$. The extremal function Ex$(v,n)$ is defined as the maximum length of all the $v$-free and $k$-sparse sequences. In this paper, we study a generalization of the extremal function Ex$(v,n)$.