{
  "id": "2009.05869",
  "version": "v1",
  "published": "2020-09-12T21:48:10.000Z",
  "updated": "2020-09-12T21:48:10.000Z",
  "title": "Longest common subsequences between words of very unequal length",
  "authors": [
    "Boris Bukh",
    "Zichao Dong"
  ],
  "comment": "32 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "We consider the expected length of the longest common subsequence between two random words of lengths $n$ and $(1-\\varepsilon)kn$ over $k$-symbol alphabet. It is well-known that this quantity is asymptotic to $\\gamma_{k,\\varepsilon} n$ for some constant $\\gamma_{k,\\varepsilon}$. We show that $\\gamma_{k,\\varepsilon}$ is of the order $1-c\\varepsilon^2$ uniformly in $k$ and $\\varepsilon$. In addition, for large $k$, we give evidence that $\\gamma_{k,\\varepsilon}$ approaches $1-\\tfrac{1}{4}\\varepsilon^2$, and prove a matching lower bound.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-12T21:48:10.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "60J05",
      "60K35"
    ],
    "keywords": [
      "longest common subsequence",
      "unequal length",
      "random words",
      "symbol alphabet",
      "matching lower bound"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 32,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}