Where the typical set partitions meet and join
Recall that the partitions of an \(n\)-element set are partially ordered by the following relation: \(p\preceq p'\) if each block of \(p'\) is the union of blocks of \(p\). It is well known that all partitions of an \(n\)-element set make a lattice, the partition lattice, with this partial order. Select \(r\) random elements of the partition lattice independently from the uniform distribution. What is the probability that their meet is the minimum partition \(p_{\min}\) whose blocks are singletons? What is the probability that their join is the maximum partition \(p_{\max}\) which has only one block? The paper has the following results: derives an exact formula for the probability that \(r\)-tuples of random partitions meet in \(p_{\min}y\), and shows that for \(r= 2\) and \(n\to\infty\) this probability approaches zero, while for \(r>2\) and \(n\to\infty\) this probability approaches one. For \(r=2\) the meet of the two random partitions does not have blocks of size 3 or higher with high probability, and the number of two-element blocks is asymptotically Poisson with parameter near \({1\over 2}\log^2n\). For every \(r\geq 2\), the joint of \(r\) random partitions is \(p_{\max}\) with probability approaching \(1\).
scientific article; zbMATH DE number 1409043