Probabilistic Extensions of the Erd\H os-Ko-Rado Property

Details Probabilistic Extensions of the Erd\H os-Ko-Rado Property Probabilistic Extensions of the Erd\H os-Ko-Rado Property

2005-09-16

arxiv.org/abs/math/0509382v1

Methodology and Computing in Applied Probability, 8, 357-371, 2006

Mathematics

Combinatorics

18 pages

Scientific paper

The classical Erd\H os-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.

Affiliated with

Also associated with

No associations

Rating

Probabilistic Extensions of the Erd\H os-Ko-Rado Property does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Probabilistic Extensions of the Erd\H os-Ko-Rado Property, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Probabilistic Extensions of the Erd\H os-Ko-Rado Property will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-553329