0
$\begingroup$

Suppose there are $n\ge 3$ distinct objects from which one or more subsets of three are chosen.

I'd like help to find the maximum number of such subsets that can be chosen so that no two of those subsets contain (at least) two objects in common. In other words two chosen subsets can have at most one object in their intersection.

For example once we choose $\{a,b,c\}$ from $\{a,b,c,d\}$, then the choice $\{a,b,d\}$ is no longer available because it matches a pair of the earlier chosen subset. Indeed it follows that for $n=4$ the maximum number of subsets we can choose is one.

Similarly for $n=6$ we can choose a maximum of four subsets.

Is it possible to attack this problem using recurrence relations? Or do we have to count the number of ways directly?

What about the general case of subsets of size $k\lt n$ instead of $3$?

$\endgroup$
  • $\begingroup$ I think it would clarify matters to solve the case of $n=4,5$ completely. For $n=4$, say, surely that isn't difficult...there are only $4$ ways to choose three objects. If your first choice is $\{a,b,c\}$ then any other choice would have to have two in common with this one, yes? So in this case the answer would be $1$, no? $\endgroup$ – lulu Jul 22 '18 at 14:10
  • $\begingroup$ See the topic balanced incomplete block designs for the special case where each pair appears exactly once in the collection of (equal sized) subsets. In considering how many subsets can be achieved where pairs appear at most once, the block designs are usually called packings. $\endgroup$ – hardmath Jul 22 '18 at 14:14
  • $\begingroup$ @hardmath Yes, you are right and I correct it. $\endgroup$ – Fermat Jul 22 '18 at 14:14
  • $\begingroup$ @lulu Yes, for n=4, the answer is 1. $\endgroup$ – Fermat Jul 22 '18 at 14:16
  • 1
    $\begingroup$ What is the desired answer for $n=6$? If my first two choices are $\{a,b,c\}$ and $\{d,e,f\}$, the answer would seem to be $2$. But if my first two choices are $\{a,b,c\}$ and $\{c,d,e\}$, I could then go on to choose $\{a,d,f\}$ and $\{b,e,f\}$ and get an answer of $4$. In other words, it's still not clear exactly what it is you want to count. $\endgroup$ – Barry Cipra Jul 22 '18 at 14:39
2
$\begingroup$

This is one combinatorial problem among many similar topics, and we begin by introducing some notation that is commonly used.

By historical connection to experimental designs, the number of distinct objects is conventionally $v$ (for varieties) and the size of the subsets making up the "blocks" is $k$. The problem here is to achieve the maximum number of blocks, subject to the restrict that no pair of objects appears in more than one block ($k$-subset). This is known as the "packing problem", and the maximum number of blocks $b$ is known as the packing number $\mathscr P(v,k)$.

[The dual problem involves choosing a collection of $k$-subsets in which each pair appears at least once. This is the covering problem. The minimum number of such blocks $b$ is called the covering number, and when there is a design with each pair appearing exactly once, the packing number and covering number agree.]

No simple formula or recurrence relation is known for the packing numbers $\mathscr P(v,k)$, although there is a well-known upper bound (the Schönheim bound) based on dividing the total number of pairs $\binom{v}{2}$ by the number pairs in one $k$-subset $\binom{k}{2}$. There is also a substantial literature on when the upper bound can be attained (Balanced Incomplete Block Designs).

A relatively recent reference (2013) for the larger cluster of problems is "Covering and packing for pairs" by Chee, Colbourn, Lee, and Wilson:

In this paper it is shown that for all sufficiently large values of $v$, a packing and a covering on $v$ elements exist whose numbers of blocks differ from the basic bounds by no more than an additive constant depending only on $k$.

Block size $\mathbf{k=3}$

The specific case of choosing subsets of size $3$ has been thoroughly examined, starting with those instances in which the upper bound can be attained:

$$ b = \frac{\binom{v}{2}}{\binom{3}{2}} = \frac{v(v-1)}{6} $$

for which the name Steiner triple systems is usual.

Here the number of pairs $v(v-1)/2$ must be divisible by $3$, which gives the necessary condition that $v\equiv 1,3 \bmod 6$. It was shown by R.C. Bose (1939) and by Th. Skolem (1958) that this necessary condition is also sufficient.

The details for the residues $v\equiv 0,2,4,5 \bmod 6$ are worked out in Chapter 4 of Design Theory 2nd Ed. by C. Lindner and C. Rodger (2008):

$$ \begin{array}{|c|c|} \hline v \bmod 6 & \mathscr{P}(v,3) \\ \hline 0\text{ or }2 & \frac{v(v-2)}{6} \\ 1\text{ or }3 & \frac{v(v-1)}{6} \\ 4 & \frac{v^2-2v-2}{6} \\ 5 & \frac{v^2-v-8}{6} \\ \hline \end{array} $$

$\endgroup$
  • 1
    $\begingroup$ Thank you @hardmath for your detailed explanation and also for giving the references. I think there is a typo in the numerator of $b=...$ since it should be $v\choose {2}$ $\endgroup$ – Fermat Jul 23 '18 at 5:55
  • 1
    $\begingroup$ @Fermat: Thanks for noticing that typo! $\endgroup$ – hardmath Jul 23 '18 at 11:38
  • $\begingroup$ You're welcome. $\endgroup$ – Fermat Jul 23 '18 at 20:43

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.