MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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