# Subsets with small interaction.

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?

-
Which of $n, N, C$, if any, are required to be finite? It makes a big difference. – Ross Millikan Dec 30 '12 at 16:36
all of them are finite positive integers – Carry on Smiling Dec 30 '12 at 16:38
Some motivation? What have you tried? – leonbloy Dec 30 '12 at 17:48
I found an upper bound: $\frac{\binom{N}{n+1}}{\binom{C}{n+1}}$ – Carry on Smiling Dec 30 '12 at 17:57

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.

-
I dont understand any of this: what do I need to learn to know this? – Carry on Smiling Dec 30 '12 at 18:08
@Khromonkey I amplified a little the answer. – leonbloy Dec 30 '12 at 18:44

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.

-