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$
1
  • $\begingroup$ I can do the case k=2 ;-) $\endgroup$
    – Mike F
    Commented May 28, 2013 at 22:34

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .