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?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ Naive probabilistic method gives something like $O(k)\cdot \frac{\binom{2k}{k}}{2^k}$ partitions. $\endgroup$
    – Fedor Petrov
    Commented 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
    Commented 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
    Commented 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$
    – Aaron Meyerowitz
    Commented Sep 26, 2017 at 4:21

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .