{
  "id": "1602.01270",
  "version": "v1",
  "published": "2016-02-03T11:29:07.000Z",
  "updated": "2016-02-03T11:29:07.000Z",
  "title": "On random partitions induced by random maps",
  "authors": [
    "Dmitry Krachun",
    "Yuri Yakubovich"
  ],
  "comment": "17 pages",
  "categories": [
    "math.PR"
  ],
  "abstract": "The lattice of the set partitions of $[n]$ ordered by refinement is studied. Given a map $\\phi: [n] \\rightarrow [n]$, by taking preimages of elements we construct a partition of $[n]$. Suppose $t$ partitions $p_1,p_2,\\dots,p_t$ are chosen independently according to the uniform measure on the set of mappings $[n]\\rightarrow [n]$. The probability that the coarsest refinement of all $p_i$'s is the finest partitions $\\{\\{1\\},\\dots,\\{n\\}\\}$ is shown to approach $1$ for any $t\\geq 3$ and $e^{-1/2}$ for $t=2$. The probability that the finest coarsening of all $p_i$'s is the one-block partition is shown to approach 1 if $t(n)-\\log{n}\\rightarrow \\infty$ and $0$ if $t(n)-\\log{n}\\rightarrow -\\infty$. The size of the maximal block of the finest coarsening of all $p_i$'s for a fixed $t$ is also studied.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2016-02-03T11:29:07.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A18",
      "06A07",
      "60C05"
    ],
    "keywords": [
      "random maps",
      "random partitions",
      "uniform measure",
      "one-block partition",
      "finest coarsening"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 17,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2016arXiv160201270K"
    }
  }
}