{
  "id": "2307.05768",
  "version": "v1",
  "published": "2023-07-11T19:51:52.000Z",
  "updated": "2023-07-11T19:51:52.000Z",
  "title": "Increasing subsequences of linear size in random permutations and the Robinson-Schensted tableaux of permutons",
  "authors": [
    "Victor Dubach"
  ],
  "comment": "34 pages",
  "categories": [
    "math.PR",
    "math.CO"
  ],
  "abstract": "The study of longest increasing subsequences (LIS) in permutations led to that of Young diagrams via Robinson-Schensted's (RS) correspondence. In a celebrated paper, Vershik and Kerov established a limit theorem for such diagrams and deduced the $2\\sqrt{n}$ estimate for the LIS of a uniformly random permutation of size $n$. Independently, Hoppen et al. introduced the theory of permutons as a scaling limit of permutations. In this paper we extend in some sense the RS correspondence of permutations to the space of permutons. When the RS-tableaux of a permuton are non-zero we obtain a linear behavior for the sampled permutations' RS-tableaux, along with some large deviation results. In particular, the LIS of sampled permutations behaves as a multiple of $n$. Finally by studying asymptotic properties of Fomin's algorithm for permutations, we show that the RS-tableaux of a permuton satisfy a partial differential equation.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2023-07-11T19:51:52.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "60C05",
      "05A05"
    ],
    "keywords": [
      "random permutation",
      "robinson-schensted tableaux",
      "linear size",
      "sampled permutations",
      "rs-tableaux"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 34,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}