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

1

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.