There are $2N$ unique balls, $2K$ of them are red, the rest are white (thus $2K \le 2N$). You divide the $2N$ balls randomly into two sets, each containing exactly $N$ elements.
Is it possible to show that there exists a constant $0 < \delta \le 1$ such that with high probability (at least $1 - K^{-c}$, $c$ is a constant), both of the partitions contain at least $(1 - \delta) K$ red balls?
I'm able to show that this holds if, instead of dividing the set of balls into two equal sized partitions, we instead throw each ball randomly into one of the two sets. In this case, I can immediately use the Chernoff's bound for independent Poisson trials and obtain a stronger result: for $\delta = (2c)^{\frac{1}{2}}$ the probability is at least $1 - e^{-cK}$. But I don't know how I should proceed with this case.
Consider the following way of distributing the ball to the two sets: consider a sequence of $2N$ initially white balls -- the first $N$ balls will be allocated to the first set, and the last $N$ balls to the second set. We will paint $2K$ balls red at random, and bound the probability that less than $(1-\delta)K$ balls in the first half are red.
Consider the following "algorithm" to paint the balls. As long as the number of red balls in the first half is less than $(1-\delta)K$, pick one ball at random from the entire sequence, and paint it red. Let $X$ be the number of iterations this algorithm proceed. We want to bound the probability that $X \ge 2K$.
Clearly, throughout the execution of this algorithm, there will be at least $N - (1-\delta)K \ge N-(1-\delta)N = \delta N$ empty bins in the first half. Thus, the probability on each iteration that one of the balls in the first half will be painted is at least $\frac{\delta N}{2N} = \frac{\delta}{2}$.
Let $Y_i$ be the random variable that takes the value of 1 if in the $i$-th iteration of the algorithm, the algorithm painted a ball in the first half red. We have $E[Y_i] \ge \frac{\delta}{2}$. Let $Y = \sum_{1 \le i \le 2K} Y_i$. We have $E[Y] = \delta K$.
Using Chernoff's bound for the sum of independent Poisson trials, we have: \begin{eqnarray*} \Pr(X \ge 2K) &\le& \Pr\left(Y \le (1-\delta) K\right) \\ &\le& \Pr(Y \le \frac{1-\delta}{\delta} E[Y]) \\ &=& \Pr(Y \le (1 - \frac{2\delta - 1}{\delta}) E[Y]) \\ &\le& e^{-\delta K (\frac{2\delta - 1}{\delta})^2 / 2} \\ &=& e^{-2\frac{(2\delta - 1)^2}{\delta}K} \end{eqnarray*}
By union bound, the probability that both of the sets contain at least $(1-\delta)K$ balls is at least $1 - 2e^{-2\frac{(2\delta - 1)^2}{\delta}K}$.