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.

Are there good lower bounds on the size of a collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common?

share|improve this question
    
Writing each set as a $0$-$1$ vector of length $n$, you are looking for a collection of strings, each containing $k$ ones, such that the Hamming distance between each pair of strings is at least $d = 2k-m$. Such a collection is usually called an error correcting code. There is a lot of literature on these, but it might be helpful if you are more specific about the kind of parameters you allow. E.g., how large is $k$ and $d$? Linear in $n$? Smaller? –  Srivatsan Dec 2 '11 at 23:05
1  
Look up the Ray-Chaudhury-Wilson theorem, which might help you. –  Yuval Filmus Dec 2 '11 at 23:49
    
Does this other account belong to you? If so, we can flag the moderators to merge the two accounts; it'll make it convenient for you to keep track of your questions. Thanks, –  Srivatsan Dec 3 '11 at 23:46
    
@Srivatsan: You are correct in that this is related to the theory of error-correcting codes. An even better match with the question is formed by the subclass of constant weight codes (some authors use the term fixed weight code). Off the top of my head I recall that there is an upper bound to the cardinality of such beasts called the Johnson bound. Don't remember any lower bounds at this time. A very combinatorial problem. –  Jyrki Lahtonen Dec 4 '11 at 8:47
1  
... and I don't understand the downvote at all. –  Jyrki Lahtonen Dec 4 '11 at 8:51
add comment

1 Answer

I suppose you mean a lower bound for the maximum size of a collection of $k$-element subsets of an $n$-element set such that each pair of subsets has at most $m$ elements in common.

As noted in the comments, this question is equivalent to finding the largest collection of binary codewords of length $n$ and weight $k$ such that the distance between any two codewords is at least $d=2(k-m)$. Graham and Sloane proved that one can construct a collection of $N$ such codewords where: $$N \geq \frac{n^{k-d+1}}{k!}$$ for sufficiently large $n$ and for fixed $k$. The construction is very pretty; see the proof in their paper. This bound is tight, in the sense that the Johnson bound gives an upperbound of $$N \leq \frac{(d-1)! \cdot n^{k-d+1}}{k1}$$

As for when $k$ and $d$ are functions of $n$, I'm not aware of good bounds.

share|improve this answer
add comment

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.