On random partitions induced by random maps

Abstract

The lattice of the set partitions of $[n]$ ordered by refinement is studied. Given a map $\varphi :[n]\to [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]\to [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\ge 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\to \infty$ and $0$ if $t(n)-\log n\to -\infty$. The size of the maximal block of the finest coarsening of all $p_i$'s for a fixed $t$ is also studied.

17 pages

References in corpus (1)

• Preservation of log-concavity on summation