{
  "id": "1904.00725",
  "version": "v1",
  "published": "2019-04-01T12:20:31.000Z",
  "updated": "2019-04-01T12:20:31.000Z",
  "title": "On the longest common subsequence of independent random permutations invariant under conjugation",
  "authors": [
    "Mohamed Slim Kammoun"
  ],
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "Bukh and Zhou conjectured that the expectation of the length of the longest common subsequence of two i.i.d random permutations of size $n$ is greater than $\\sqrt{n}$. We prove in this paper that there exists a universal constant $n_1$ such that their conjecture is satisfied for any pair of i.i.d random permutations of size greater than $n_1$ with distribution invariant under conjugation. We prove also that asymptotically, this expectation is at least of order $2\\sqrt{n}$ which is the asymptotic behaviour of the uniform setting. More generally, in the case where the laws of the two permutations are not necessarily the same, we gibe a lower bound for the expectation. In particular, we prove that if one of the permutations is invariant under conjugation and with a good control of the expectation of the number of its cycles, the limiting fluctuations of the length of the longest common subsequence are of Tracy-Widom type. This result holds independently of the law of the second permutation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-04-01T12:20:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05"
    ],
    "keywords": [
      "longest common subsequence",
      "independent random permutations invariant",
      "conjugation",
      "expectation",
      "distribution invariant"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}