Probability that random subsets will have an intersection of a certain size I'm currently reading a paper and in one of it proofs (page 17) it states the following without much explanation:
Let $l(k) = \frac{1}{2} \log^2{k}$.
Let both $A \subset [k^2]$ and $B \subset [k^2]$ be subsets of size $k \cdot \log{k}$, where $[k^2] = \{1, \dots, k^2 \}$.
The paper states that by Chernoff bound the probability that $\vert A \cap B \vert < l(k)$ is $2^{-\Omega(l(k))}$.
Could somebody explain in detail how this statement is derived and how the Chernoff bound is applied here?
 A: Given the way the sets are chosen (uniformly are random among sets of a specific size, instead of choosing every element to be in the set independently), this does not follow directly from a Chernoff bound, but due to the properties of sampling without replacement (specifically, negative correlations, which make things even "better" in terms of concentration) the bound will be the same as in that of sampling with replacement, where we can use Chernoff bounds.
Suppose each element is put independently at random in $A$ (similarly for $B$) with probability $p\stackrel{\rm def}{=}\frac{\log k}{k}$, so that $$\mathbb{E}[\lvert A\rvert] = \mathbb{E}[\lvert B\rvert] = pk^2 = k\log k$$
and the size are actually tighly concentrated around this expected value.
Let, for element $i\in[k^2]$, $X_i$ denote the indicator random variable equal to $1$ iff $i\in A\cap B$. Then, by independencce of the choices of $A$ and $B$, we have
$$
\mathbb{E}[X_i] = \Pr[i\in A\text{ and } i\in B] = p^2
$$
and we can apply a Chernoff bound to the random variable $\lvert A\cap B\rvert=\sum_{i=1}^{k^2} X_i$, which is a sum of independent random variables in $\{0,1\}$. Note that $\mathbb{E}[\lvert A\cap B\rvert] = k^2p^2 = \log^2 k = 2l(k)$.
$$
\Pr[\lvert A\cap B\rvert < l(k)]
= \Pr[\lvert A\cap B\rvert < \frac{1}{2}\mathbb{E}[\lvert A\cap B\rvert]] \leq e^{-\frac{1}{4}\mathbb{E}[\lvert A\cap B\rvert]/2}
=e^{-\frac{1}{4}l(k)}  = 2^{-\Omega(l(k))}
$$
