For a set $X$ of cardinality $N$: how can we find a set of subsets of $X$ of cardinality $C$ such that no two subsets have an intersection of more than $n$ elements? What is the largest cardinality of the aforementioned set?
Subsets with small interaction.
-
0I found an upper bound: $\frac{\binom{N}{n+1}}{\binom{C}{n+1}}$ – 2012-12-30
2 Answers
Each subset can be put in correspondence with a binary vector of length $N$, with weight (number of ones) $C$. For example, say $N=5$ and $C=3$, the vector $v=[1, 0 , 0 , 1 , 1]$ (length=5, weight=3), corresponds to selecting the elements 1, 4 and 5. Clearly, there are ${5 \choose 3}$ such vectors.
But we have the additional requisite of an intersection of at most $n$ elements for each pair. This is equivalent of having at most $n$ ones in common, or at least $2(C-n)$ different elements. Then, in the binary-codes language, we are after a constant weight code (weight $C$ , length $N$) with minimum Hamming distance of $d = 2(C-n)$. This is a well known and difficult problem; there are some bounds, tables and more.
-
0@Khromonkey I amplified a little the answer. – 2012-12-30
Here are two observations I have made:
We can add all of the subsets of size $n-1$ without any problems. Once we have done that we should add all of size $n$ as possible and never add any larger sets. So the problem is equivalent to finding the maximum number of subsets all of cardinality $n+1$ we can fit.