4
$\begingroup$

Given a set S of n elements. What is the largest number of k-element subsets of S such that every pair of these subsets has at most one common element?

$\endgroup$
  • $\begingroup$ I can do the case k=2 ;-) $\endgroup$ – Mike F May 28 '13 at 22:34
1
$\begingroup$

To every $k-$subset, associate the $k \choose 2$ subsets of pairs of elements. From the conditions in the question, every 2 $k-$subsets must have distinct pairs, hence there are at most $\frac{n\choose2} {k \choose 2} = \frac{n(n-1)}{k(k-1)}$ such sets. Note that this need not be an integer.

To get much better bounds, you will need to start to know what $n$ and $k$ are. For example, with $k=2$, we can get $\frac {n(n-1)}{2(1) }$ subsets easily. With $k> \frac{n}{2}$, we can only get 1 set, even though the above gives us a bound of $\approx 4$ if $k$ is close to $\frac{n}{2}$, and a bound of 1 if $k$ is close to $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.