{
  "id": "1311.1594",
  "version": "v1",
  "published": "2013-11-07T08:07:47.000Z",
  "updated": "2013-11-07T08:07:47.000Z",
  "title": "A generalization of the extremal function of the Davenport-Schinzel sequences",
  "authors": [
    "Kok Bin Wong",
    "Cheng Yeaw Ku"
  ],
  "comment": "8 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "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)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-11-07T08:07:47.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extremal function",
      "davenport-schinzel sequences",
      "generalization",
      "sparse sequences",
      "maximum length"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 8,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1311.1594W"
    }
  }
}