existence of $(K,\alpha)$-disperser with degree $D=O(\log\frac{N}{K})$ A bipartite graph $G=(V_1=[N],V_2=[M],E)$ is a $(K,\alpha)$-disperser if for every $X\subseteq V_1$ of cardinality $K$, $|\Gamma(X)|>(1-\alpha)M$. That is, every large enough set in $V_1$ misses less than an $\alpha$-fraction of the vertices in $V_2$.
Prove that for every $M\leq K\leq N$ and constant $0\lt\alpha\lt1$ there exists a $(K,\alpha)$-disperser $G=(V_1=[N],V_2=[M],E)$ with degree $D=O(\log\frac{N}{K})$.
 A: We prove the existence using the probabilistic method, with the simplest possible construction - for each $v \in V_1$ pick $D$ neighbours uniformly at random and independently from $V_2$. Fix $X \subseteq V_1, |X| = K, Y \subseteq V_2, |Y| = \alpha M, D = c \log N/K$ (we will pick the constant later). We first want to compute the probability that $\Gamma(X) \cap Y = \phi$. Pick $x \in X, y \in Y$, and observe that $\Pr[x \not\sim y] = 1 - \frac{D}{M}$. As all edges are drawn independently, we get that: $$\Pr[\Gamma(X) \cap Y = \phi] = \Pr[\forall x \in X, y\in Y \ : \ x \not\sim y] = (1 - \frac{D}{M})^{|X| \cdot |Y|} = (1 - \frac{D}{M})^{K \alpha M} = (1 - \frac{1}{M/D})^{(M/D) \alpha K D} \approx e^{-\alpha KD}$$ We now apply a crude union bound as follows:
\begin{align}
\Pr[G \text{ is not } (K,\alpha)-disperser] & = \Pr[\exists X \subseteq V_1, Y \subseteq V_2, |X| = K, |Y| = \alpha M \ : \ \Gamma(X) \cap Y = \phi] \\
& \leq \sum_{\stackrel{X \subseteq V_1}{|X|=K}} \sum_{\stackrel{Y \subseteq V_2}{|Y|=\alpha M}} \Pr[\Gamma(X) \cap Y = \phi] \\
& = \tbinom{N}{K} \tbinom{M}{\alpha M} e^{-\alpha KD} \\
& \leq \left(\frac{eN}{K}\right)^K \left(\frac{eM}{\alpha M}\right)^{\alpha M} e^{-\alpha KD} \\
& = e^{K+ K\log N/K+\alpha M + \alpha M \log \alpha - \alpha K D} \\
& \leq e^{4 K \log N/K - \alpha K D} \\
& = e^{4 K \log N/K - \alpha K c \log N/K} 
\end{align}
We now see that if we pick $c = 5/\alpha$ for example, we will get: $$\Pr[G \text{ is not } (K,\alpha)-disperser] \leq e^{-K \log N/K} < 1$$ And therefore there exists such a $(K,\alpha)$-disperser with the desired parameters (in fact, a random graph drawn in this manner is a.a.s a disperser)
