Where the typical set partitions meet and join
type: Item
instance of: scholarly article
title: Where the typical set partitions meet and join
zbMATH Open document ID: 0940.05007
published in: The Electronic Journal of Combinatorics
publication date: 2000-03-01T00:00:00Z
full work available at URL: https://eudml.org/doc/120386
full work available at URL: v7i1r5.html
review text: 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\).
Mathematics Subject Classification ID: 05A18
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 1409043
zbMATH Keywords: set partition lattice
zbMATH Keywords: join operations
zbMATH Keywords: enumeration
zbMATH Keywords: random
zbMATH Keywords: limiting probabilities
zbMATH Keywords: random partitions
author: Boris Pittel
reviewed by: László A. Székely
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1409043