Minimal number of possible set packings from k-element subsets of r*k sized set

Question

I have a question I am trying to figure out but I'm having a difficult time finding the answer.

Say I have a set $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ so that $n= r*k = |S|$ and $r=3, k=3$. I take all possible k-element subsets of S for a total of $\frac{{9 \choose 3}*{6 \choose 3}}{3!}=280$ different combinations of subsets.

What I'm trying to figure out is: what is the minimum number of times we can pick a combination of subsets such that it packs (all subsets are disjoint) the set $S$ and no subset is picked more than once?

The maximum number of times this is possible is $\frac{n!}{k!(n-k)!}*\frac{k}{n}$, since this is the amount of possible combinations divided by the amount of subsets removed after each cover. For the case with $r,k=3$ this is 28 times.

I have tried handling the problem as a complete hypergraph and then removing perfect matchings until this is no longer possible but I cannot find any literature for this specific case. There are a lot of exisiting theories for checking whether or not a hypergraph has a perfect matching but these do not perfectly apply to this specific case.

I have via a random algorithm estimated that the minimum should be about 20 times. However I am at a loss how to find the mathematical motivation! Kind regards

Answer 1

If I understand correctly, you want to find the independent domination number of a graph with one node per partition and an edge for each pair of partitions that share a part.

For $n=9$ and $k=3$, the value is $16$, obtained via integer linear programming:

{{0,1,2}, {3,4,5}, {6,7,8}}
{{0,1,4}, {2,7,8}, {3,5,6}}
{{0,1,5}, {2,6,7}, {3,4,8}}
{{0,1,6}, {2,3,4}, {5,7,8}}
{{0,1,8}, {2,3,5}, {4,6,7}}
{{0,2,4}, {1,6,7}, {3,5,8}}
{{0,2,5}, {1,7,8}, {3,4,6}}
{{0,2,6}, {1,3,5}, {4,7,8}}
{{0,2,8}, {1,3,4}, {5,6,7}}
{{0,3,7}, {1,4,6}, {2,5,8}}
{{0,4,5}, {1,2,7}, {3,6,8}}
{{0,4,6}, {1,3,8}, {2,5,7}}
{{0,4,8}, {1,5,7}, {2,3,6}}
{{0,5,6}, {1,4,7}, {2,3,8}}
{{0,5,8}, {1,3,6}, {2,4,7}}
{{0,6,8}, {1,2,3}, {4,5,7}}