Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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 –  Bananarama 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}}$ –  Bananarama Dec 30 '12 at 17:57

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
I dont understand any of this: what do I need to learn to know this? –  Bananarama 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.