Premium
Partial covering arrays and a generalized Erdös‐Ko‐Rado property
Author(s) -
Carey Particia A.,
Godbole Anant P.
Publication year - 2010
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.20244
Subject(s) - combinatorics , mathematics , property (philosophy) , pairwise comparison , statistics , epistemology , philosophy
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 \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${{{n}}}{-}{{{1}}}\choose{{{{k}}}{-}{{{1}}}}$\end{document} . 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 of k ‐subsets of [ n ] that satisfies the following property: For each A, B, C ∈ , 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). © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 155–166, 2010