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

1 Answer 1

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 agree to our terms of service and acknowledge you have read our privacy policy.

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