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
    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.2011-05-05
  • 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
    Interesting, thanks. But how the $(T_n(i))_i$ turn out to be i.i.d? Can you elaborate a bit on that?2011-05-06
  • 0
    Corrected, thanks.2011-05-06
  • 0
    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$) ?2011-05-06
  • 0
    Which is why using the random variables $T_n(t)$ might be more promising.2011-05-06