Partial Covering Arrays and a Generalized Erdo′S - Ko - Rado Property
Document Type
Article
Publication Date
1-1-2010
Description
The classical Erdös-Ko-Rado theorem states that if k≤ ⌊n/2⌋ then the largest family of pairwise intersecting k-subsets of [n]={1,. ,n} is of size (n-1 k-1). A family of k subsets satisfying this pairwise intersecting property is called an EKR family. We generalize the EKR property and provide asymptotic lower bounds on the size of the largest family A of k-subsets of [n] that satis es the following property: For each A,B,CεA, each of the four sets A∩B∩C; A∩B∩C̃; A∩B̃∩C;Ã ∩B∩C are non-empty. This generalized EKR (GEKR) property is motivated, generalizations are suggested, and a comparison is made with fixed weight 3-covering arrays. Our techniques are probabilistic, and reminiscent of those used in (A. Godbole, D. Skipper, and R. Sunley, Comb Prob Computing 5 (1996), 105-118) and in the work of Roux, as cited in (N. J. A. Sloane, J Comb Designs 1 (1993), 51-63).
Citation Information
Carey, Particia A.; and Godbole, Anant P.. 2010. Partial Covering Arrays and a Generalized Erdo′S - Ko - Rado Property. Journal of Combinatorial Designs. Vol.18(3). 155-166. https://doi.org/10.1002/jcd.20244 ISSN: 1063-8539