6
$\begingroup$

I am given $2n$ $3-$element subsets of $\{1,2,...,n\}$ that were chosen uniformly and independently at random (out of all possible 3-element subsets). How can I prove that with probability $\geq 1-e^{-\Theta(n)}$ one can select $n$ subsets out of the total $2n$, such that no element of $\{1,2,...,n\}$ appears in more than $40$ subsets?

I'm pretty sure that a Chernoff bound should be used here, but I couldn't get rid of the dependency between the random variables...

Any ideas..?

  • 0
    Thanks. How do you analyse such a process? Anyway, I'm still guessing the solution should be rather elementary...2011-05-05

1 Answers 1

4

Poissonization might be the way.

Instead of choosing exactly $2n$ triplets, draw uniformly at random $X_n$ triplets, where $X_n$ has Poisson $cn$ distribution. Here and later on, write whp for with high probability in the sense that the probability of the considered event is $\ge1-2^{-\Theta(n)}$. For example, $X_n\ge2n$ whp if $c>2$, hence if we can select $n$ triplets amongst these $X_n$ such that no vertex belongs to more than $k=40$ of them, we are done.

For every triplet $t$, let $T_n(t)$ denote the number of times $t$ was chosen. For every vertex $i$, let $T_n(i)$ denote the sum of $T_n(t)$ over the triplets $t$ such that $i\in t$, hence $T_n(i)$ is the number of triplets $i$ belongs to.

Conditionally on $X_n$, $T_n(t)$ is binomial $(X_n,1/b_n)$ with $b_n={n\choose 3}$ hence, unconditionally, the $(T_n(t))_t$ are i.i.d. random variables with Poisson $cn/b_n\approx6c/n^2$ distribution. Each $T_n(i)$ is the sum of ${n-1\choose 2}$ i.i.d. $T_n(t)$ hence $T_n(i)$ is Poisson with parameter ${n-1\choose 2}cn/b_n=3c$.

Maybe you can continue from here.

  • 0
    Which is why using the random variables $T_n(t)$ might be more promising.2011-05-06