Probabilistic extensions of the Erdős-Ko-Rado property

DOI10.1007/S11009-006-9751-2MaRDI QIDQ861532zbMATH OpenOpenAlexFDO

Authors Anna Celaya, Anant P. Godbole, Mandy Rae Schleifer

Publication date 29 January 2007

Published in Methodology and Computing in Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0509382

zbMATH Keywords

Poisson distributionPairwise nonempty intersectionErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Central limit and other weak theorems (60F05) Combinatorial probability (60C05) Extremal set theory (05D05) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: The classical ErdH 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-1choose 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,\mathrm{...},X_b)$ can be approximated by a multidimensional Poisson vector with independent components.

Recommendations

• On the stability of the Erdös-Ko-Rado theorem
• On Erdős-Ko-Rado for random hypergraphs. I
• Erdős-Ko-Rado in random hypergraphs
• Partial covering arrays and a generalized Erdős-Ko-Rado property
• A multiply intersecting Erdős-Ko-Rado theorem -- the principal case

Cites work

• scientific article; zbMATH DE number 51878 (Why is no real title available?)
• A New Short Proof of Kneser's Conjecture
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Random covering designs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(4)

• An extension of the Landau-Kolmogorov inequality. Solution of a problem of Erdős
• Partial covering arrays and a generalized Erdős-Ko-Rado property
• Erdős-Littlewood-Offord problem with arbitrary probabilities
• Probability measures with reflection coefficients \(\{a_n\} \in \ell^4\) and \(\{a_{n+1}-a_n\} \in \ell^2\) are Erdős measures

This page was built for publication: Probabilistic extensions of the Erdős-Ko-Rado property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q861532)