# 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 –  user4140 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}}$ –  user4140 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.