Family hitting r-sets

40 Views Asked by At

I'll start with a definition.

We say a family $\mathcal{F}\subseteq [n]^{(k)}$ hits every $r$-set for some $r\geq k$ if for each $R\in[n]^{(r)}$, there exists $F\in \mathcal{F}$ such that $F\subseteq R$.

First of all, I am tasked with finding the smallest family of 2-sets which hits all 3-sets in $[7]^{(3)}$. I've found such a family of size 9, but how do I know it is the smallest? If it is not the smallest, how do I find the smallest? I assume it has to do with Turan's theorem, but I'm not sure I understand that well enough.

The method I used was using a greedy algorithm, but I don't think that always gives you the smallest such family.