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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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