Probabilistic Extensions of the Erdős–Ko–Rado Property

The classical Erdős–Ko–Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size $n\ (n > 2k)$ , then the largest possible pairwise intersecting family has size $t ={n-1\choose k-1}$ . We consider the probability that a randomly selected family of size t=t n has the EKR property (pairwise nonempty intersection) as n and k=k n tend to infinity, the latter at a specific rate. As t gets large, the EKR property is less likely to occur, while as t gets smaller, the EKR property is satisfied with high probability. We derive the threshold value for t using Janson’s inequality. Using the Stein–Chen method we show that the distribution of X 0, defined as the number of disjoint pairs of subsets in our family, can be approximated by a Poisson distribution. We extend our results to yield similar conclusions for X i , the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution (X 0, X 1, ..., X b ) can be approximated by a multidimensional Poisson vector with independent components.