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

Abstract

Let $[n]=\{1,\dots ,n\}$. A sequence $u=a_1{a}_2\dots a_l$ over $[n]$ is called $k$-sparse if $a_i=a_j$, $i>j$ implies $i-j\ge 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)$.

8 pages

References in corpus (2)

• Tight bounds on the maximum size of a set of permutations with bounded VC-dimension
• On Multiple Pattern Avoiding Set Partitions