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..?

  • $\begingroup$ Just a vague idea, but perhaps it can be modelled as a probability process, in which two 3-subsets are chosen (duplicates allowed?) at each step and the minimum of the maximum number of times any one element of $\{1,2,...,n\}$ appears (taken over all $n$ subsets of the total $2n$ at step $n$) is the outcome. $\endgroup$
    – hardmath
    May 5 '11 at 13:22
  • $\begingroup$ Thanks. How do you analyse such a process? Anyway, I'm still guessing the solution should be rather elementary... $\endgroup$
    – toko
    May 5 '11 at 13:50

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.

  • $\begingroup$ Interesting, thanks. But how the $(T_n(i))_i$ turn out to be i.i.d? Can you elaborate a bit on that? $\endgroup$
    – toko
    May 6 '11 at 7:28
  • $\begingroup$ Corrected, thanks. $\endgroup$
    – Did
    May 6 '11 at 7:42
  • $\begingroup$ If the variables $(T_n(i))_i$ are not i.i.d., isn't the situation more or less equivalent to the original setting in which $(T_n(i))_i$ were (non i.i.d.) binomial variables (with the same expectation $3c = 6$) ? $\endgroup$
    – toko
    May 6 '11 at 10:27
  • $\begingroup$ Which is why using the random variables $T_n(t)$ might be more promising. $\endgroup$
    – Did
    May 6 '11 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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