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?
Bounds on the size of these intersecting set families
-
0Writing 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
-
1Look up the Ray-Chaudhury-Wilson theorem, which might help you. – 2011-12-02
-
0Does [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
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.