8
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ Naive probabilistic method gives something like $O(k)\cdot \frac{\binom{2k}{k}}{2^k}$ partitions. $\endgroup$ – Fedor Petrov Sep 24 '17 at 13:34
  • 2
    $\begingroup$ @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. $\endgroup$ – RaphaelB4 Sep 25 '17 at 13:43
  • $\begingroup$ I thought to get a covering using idea in this question. math.stackexchange.com/questions/2441363/… $\endgroup$ – Ashot Sep 25 '17 at 14:41
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Aaron Meyerowitz Sep 26 '17 at 4:21
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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