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?

  • 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 (Wayback Machine) 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.