{
  "id": "1012.1819",
  "version": "v2",
  "published": "2010-12-08T18:11:30.000Z",
  "updated": "2011-07-26T20:46:46.000Z",
  "title": "On the Lipschitz Constant of the RSK Correspondence",
  "authors": [
    "Nayantara Bhatnagar",
    "Nathan Linial"
  ],
  "comment": "Updated presentation based on comments made by reviewers. Accepted for publication to JCTA",
  "journal": "Journal of Combinatorial Theory, Series A, 119(1):63-82, 2012",
  "categories": [
    "math.CO"
  ],
  "abstract": "We view the RSK correspondence as associating to each permutation $\\pi \\in S_n$ a Young diagram $\\lambda=\\lambda(\\pi)$, i.e. a partition of $n$. Suppose now that $\\pi$ is left-multiplied by $t$ transpositions, what is the largest number of cells in $\\lambda$ that can change as a result? It is natural refer to this question as the search for the Lipschitz constant of the RSK correspondence. We show upper bounds on this Lipschitz constant as a function of $t$. For $t=1$, we give a construction of permutations that achieve this bound exactly. For larger $t$ we construct permutations which come close to matching the upper bound that we prove.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2011-07-26T20:46:46.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rsk correspondence",
      "lipschitz constant",
      "upper bound",
      "young diagram",
      "largest number"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1012.1819B"
    }
  }
}