2
$\begingroup$

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?

  • 0
    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?2011-12-02
  • 1
    Look up the Ray-Chaudhury-Wilson theorem, which might help you.2011-12-02
  • 0
    Does [this other account](http://math.stackexchange.com/questions/88070/) 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,2011-12-03
  • 0
    @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](http://en.wikipedia.org/wiki/Constant-weight_code) (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.2011-12-04
  • 1
    ... and I don't understand the downvote at all.2011-12-04

1 Answers 1