Skip to main content
added 74 characters in body
Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \exp\left(-N\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right).$$ If $p<1/\binom{n}d$, with positive probability each $d$-set is covered by one of $n/2$-sets. So, if $$N>\frac{\binom{n}{n/2}}{\binom{n-d}{n/2-d}}\log\binom{n}d=\frac{\binom{n}{d}}{\binom{n/2}{d}}\log\binom{n}d,$$ thiswith positive probability we get the desired property of our collection. This is worse than Dustin G. Mixon's lower bound by a multiple $\log\binom{n}d$.

Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \exp\left(-N\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right).$$ If $p<1/\binom{n}d$, with positive probability each $d$-set is covered by one of $n/2$-sets. So, if $$N>\frac{\binom{n}{n/2}}{\binom{n-d}{n/2-d}}\log\binom{n}d=\frac{\binom{n}{d}}{\binom{n/2}{d}}\log\binom{n}d,$$ this is worse than Dustin G. Mixon's lower bound by a multiple $\log\binom{n}d$.

Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \exp\left(-N\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right).$$ If $p<1/\binom{n}d$, with positive probability each $d$-set is covered by one of $n/2$-sets. So, if $$N>\frac{\binom{n}{n/2}}{\binom{n-d}{n/2-d}}\log\binom{n}d=\frac{\binom{n}{d}}{\binom{n/2}{d}}\log\binom{n}d,$$ with positive probability we get the desired property of our collection. This is worse than Dustin G. Mixon's lower bound by a multiple $\log\binom{n}d$.

Source Link
Fedor Petrov
  • 108.9k
  • 9
  • 264
  • 459

Choose $N$ $n/2$-sets at random (repetitions allowed). The probability that a given $d$-set $T$ is not covered by them equals $$p=\left(1-\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right)^N\leqslant \exp\left(-N\frac{\binom{n-d}{n/2-d}}{\binom{n}{n/2}}\right).$$ If $p<1/\binom{n}d$, with positive probability each $d$-set is covered by one of $n/2$-sets. So, if $$N>\frac{\binom{n}{n/2}}{\binom{n-d}{n/2-d}}\log\binom{n}d=\frac{\binom{n}{d}}{\binom{n/2}{d}}\log\binom{n}d,$$ this is worse than Dustin G. Mixon's lower bound by a multiple $\log\binom{n}d$.