Partial covering arrays and a generalized Erdös-Ko-Rado property
✍ Scribed by Particia A. Carey; Anant P. Godbole
- Publisher
- John Wiley and Sons
- Year
- 2010
- Tongue
- English
- Weight
- 136 KB
- Volume
- 18
- Category
- Article
- ISSN
- 1063-8539
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
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