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