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