tailieunhanh - Báo cáo toán học: "WHERE THE TYPICAL SET PARTITIONS MEET AND JOIN"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: WHERE THE TYPICAL SET PARTITIONS MEET AND JOIN. | WHERE THE TYPICAL SET PARTITIONS MEET AND JOIN. Boris Pittel Received May 16 1999 Accepted January 15 2000 Abstract. The lattice of the set partitions of n ordered by refinement is studied. Suppose r partitions P1 . pr are chosen independently and uniformly at random. The probability that the coarsest refinement of all Pi s is the finest partition 1 . . . n is shown to approach 0 for r 2 and 1 for r 3. The probability that the finest coarsening of all Pi s is the one-block partition is shown to approach 1 for every r 2. Introduction. Let nn be the set of all set partitions of n ordered by refinement. That is for two partitions p and p0 p p0 if each block of p0 is a union of blocks of p. It is well known Stanley 6 that nn is a lattice it means that every pair of partitions p p0 has the greatest lower bound inf p p0 p inf p0 or p meet p0 and the least upper bound sup p p0 psupp0 or p join p0 . Namely inf p p0 is the partition whose blocks are the pairwise intersections of blocks of p and p0 and it is the coarsest simultaneous refinement of p and p0. sup p p0 is a partition whose every block is both a union of blocks of p and a union of blocks of p0 with no proper subset of the block having that property so it is the finest coarsening of p and p0. Assigning to each p the same probability 1 nn we transform nn into the probability space with uniform measure. There is a sizeable literature on the properties of the uniformly distributed partition see Pittel 5 and the references therein. Closer to the subject of this paper Canfield and Harper 1 and Canfield 2 used the probabilistic tools to find the surprisingly sharp bounds for the length of the largest antichain in nn. In 5 we proved that the total number of refinements of the random partition is asymptotically lognormal. In the present paper we study the properties of inf _ pi sup1 i r pi under the assumption that the uniform partitions p1 . pr are independent. Formally we study 1991 Mathematics Subject Classification.