Timeline for The minimal number of partitions to cover all $k$ tuples
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 26, 2017 at 4:21 | comment | added | Aaron Meyerowitz | 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.$ | |
| Sep 25, 2017 at 21:26 | answer | added | Fedor Petrov | timeline score: 7 | |
| Sep 25, 2017 at 14:41 | comment | added | Ashot | I thought to get a covering using idea in this question. math.stackexchange.com/questions/2441363/… | |
| Sep 25, 2017 at 13:43 | comment | added | RaphaelB4 | @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. | |
| Sep 25, 2017 at 4:33 | history | edited | Michael Hardy | CC BY-SA 3.0 |
edited body
|
| Sep 24, 2017 at 13:34 | comment | added | Fedor Petrov | Naive probabilistic method gives something like $O(k)\cdot \frac{\binom{2k}{k}}{2^k}$ partitions. | |
| Sep 24, 2017 at 12:14 | history | asked | Ashot | CC BY-SA 3.0 |