# The minimal number of partitions to cover all $k$ tuples

The set $N=\{1, 2, \ldots, 2k\}$ can be partitioned into pairs (e.g $(1,2),(3,4),\ldots,(2k-1,2k)$) in $\frac{(2k)!}{k!2^k}$ ways.

$k$-tuple is subset of size $k$ in $N$. We say that $k$-tuple is covered by partition $\alpha$ if none of pairs of $\alpha$ are in that tuple. For example $(2,4,\ldots,2k)$ tuple is covered by the partition above but $(1,2,\ldots,k)$ is not.

I am interested in the following problem:

Find the minimal number of partitions of the set $N$ so that all $k$ tuples are covered.

There are $2k\choose k$ tuples and every partition covers $2^k$ tuples so the answer is $\ge \frac{2k\choose k}{2^k}$. I hope to find an upper bound that is $c\frac{2k\choose k}{2^k}$ where $c$ is constant. Can anybody help on this problem?

• Naive probabilistic method gives something like $O(k)\cdot \frac{\binom{2k}{k}}{2^k}$ partitions. – Fedor Petrov Sep 24 '17 at 13:34
• @FedorPetrov , I think your probabilistic method is not that naive and your should write it down. May be it is the best one can do. – RaphaelB4 Sep 25 '17 at 13:43
• I thought to get a covering using idea in this question. math.stackexchange.com/questions/2441363/… – Ashot Sep 25 '17 at 14:41
• Note that $\frac{2k\choose k}{2^k} \approx \frac{2^k}{\sqrt{\pi k}}$ So one could try to find $2^k$ partitions into pairs that work. If so then one would have a solution with $O(\sqrt{k})\cdot\frac{2k\choose k}{2^k}$ partitions into pairs. No obvious construction for $2^k$ pairwise partitions occurs to me, even in the case $k=2^j.$ – Aaron Meyerowitz Sep 26 '17 at 4:21

Denote $N=\frac{2k\choose k}{2^k}$ and choose, say $m=\lceil 10kN\rceil$ independent random partitions (all partitions have equal probability $1/(2k-1)!!$). For any $k$-set $A$, the probability that it is not covered by a single partition equals $1/N$ (indeed, if we denote this probability by $p$, then it does not depend of $A$, and summing up by all choices of $A$ we get $\binom{2k}kp=2^k$, since any partition covers $2^k$ subsets), thus the probability that it is not covered by any of our partitions equals $(1-1/N)^{m}<e^{-10k}$. Summing up by all $2k\choose k$ subsets $A$, we see that the probability that a not covered subset exists does not exceed ${2k\choose k}e^{-10k}<4^ke^{-10k}<1$. Therefore there exists a suitable choice of $m$ partitions.