pith. sign in

arxiv: math/0512139 · v1 · pith:OTUK77X2new · submitted 2005-12-06 · 🧮 math.CO

Partial covering arrays and a generalized Erdos-Ko-Rado property

classification 🧮 math.CO
keywords propertyfamilysubsetsarrayscoveringgeneralizedintersectinglargest
0
0 comments X
read the original abstract

The classical Erd\H os-Ko-Rado theorem states that if $k\le\floor{n/2}$ then the largest family of pairwise intersecting $k$-subsets of $[n]=\{0,1,...,n\}$ is of size ${{n-1}\choose{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 ${\cal A}$ of $k$-subsets of $[n]$ that satisfies the following property: For each $A,B,C\in{\cal A}$, each of the four sets $A\cap B\cap C;A\cap B\cap C^C; A\cap B^C\cap C; A^C\cap B\cap 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.