3
$\begingroup$

Let '$n$-set' mean 'a set with $n$ elements'.

May we choose $77=\frac16\binom{11}5$ 5-subsets of 11-set $M$ such that any 6-subset $A\subset M$ contains unique chosen subset? Positive answer to analogous question for $(6m+5)$-ground set, $m>1$, is also of interest.

Maybe, something is known (I guess, at least something should be known) in a general situation: when there exists a family $\mathcal F$ of $a$-subsets in an $n$-set $M$ such that any $b$-subset of $M$ contains exactly $k$ subsets of $\mathcal F$?

$\endgroup$

2 Answers 2

9
$\begingroup$

The answer to the first question is "no." Suppose $|M|=11$ and $\mathcal S\subset\binom M5$ and $|\mathcal S|=77.$ Since each $5$-set contains five $4$-sets, and since $77\cdot5=385\gt330=\binom{11}4,$ by the pigeonhole principle some $4$-set must be contained in two members of $\mathcal S,$ which are both contained in the same $6$-set.

$\endgroup$
8
$\begingroup$

Switching to complements, the question is if we can choose 77 6-subsets of an 11-set $M$ such that any 5-subset of $M$ is contained in a chosen 6-subset (it is clear that this subset would be unique because $77\cdot 6 = \binom{11}{5}$). These are called covering designs and the question is if $C(11,6,5)=77$.

The answer is "No". In fact, it is known that $$96 \leq C(11,6,5) \leq 100.$$ See La Jolla Covering Repository.

$\endgroup$

You must log in to answer this question.

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