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.
Citation Information
Celaya, Anna; Godbole, Anant P.; and Schleifer, Mandy Rae. 2006. Probabilistic Extensions of the Erdos-Ko-Rado Property. Methodology and Computing in Applied Probability. Vol.8(3). 357-371. https://doi.org/10.1007/s11009-006-9751-2 ISSN: 1387-5841