Probabilistic Extensions of the Erdos-Ko-Rado Property

Document Type

Conference Proceeding

Publication Date

9-1-2006

Description

The classical Erdos-Ko-Rado (EKR) Theorem states that if we choose a family of subsets, each of size k, from a fixed set of size (n > 2k), then the largest possible pairwise intersecting family has size t = (k-1n-1). We consider the probability that a randomly selected family of size t = tn has the EKR property (pairwise nonempty intersection) as n and k = kn 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 X0, 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 Xi, the number of pairs of subsets that overlap in exactly i elements. Finally, we show that the joint distribution X0, X1, ⋯, Xb) can be approximated by a multidimensional Poisson vector with independent components.

Share

COinS