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: Convergence in distribution for subset counts between random sets. | Convergence in distribution for subset counts between random sets Dudley Stark School of Mathematical Sciences Queen Mary University of London London E1 4NS United Kingdom Submitted Jan 8 2003 Accepted Aug 27 2004 Published Sep 9 2004 Mathematics Subject Classifications 60C05 60F05 Abstract Erdos posed the problem of how many random subsets need to be chosen from a set of n elements each element appearing in each subset with probability p 1 2 in order that at least one subset is contained in another. Renyi answered this question but could not determine the limiting probability distribution for the number of subset counts because the higher moments diverge to infinity. The model considered by Renyi with p arbitrary is denoted by P m n p where m is the number of random subsets chosen. We give a necessary and sufficient condition on p n and m n for subset counts to be asymptotically Poisson and find rates of convergence using Stein s method. We discuss how Poisson limits can be shown for other statistics of P m n p . 1 Introduction Erdos posed the following problem which Renyi 5 solved. Subsets S1 S2 . Sm are chosen randomly from the set 1 n 1 2 3 . n where m n 1. For each r E 1 n and i E 1 m the event Ari r E Si has probability P Ar i 1 2 and the Ari are mutually independent. How large does m m n need to be so that the probability approaches 1 that Si c Sj for some pair i j E 1 m i j The model studied by Renyi with P Ar i p will be denoted by P m n p and may be considered to be a model of a random Boolean lattice when sets Si containing identical elements are identified. A different random lattice model has been studied recently in 3 4 for example in which each of the possible 2n subsets are present independently and with probability p. Let X be the number of pairs Si Sj 1 i j n for which either Si c Sj or Sj c Si. If we define I i j i j E 1 n i j by I ij I Si c Sj where I equals 1 if THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R59 1 .
