Let $U = [n]$ and $V = [m]$ be sets of nodes with $n > m$ and $E = U\times V$ be a set of edges. Let $\mathcal{N}(S)$ be the set of neighbors of a subset $S$ from $U$ or $V$.
Call a graph $G = (U, V, E)$ $d$-regular if it is bipartite and if $\mathcal{N}(j) = d$ for all $j \in U$.
Now, call a $d$-regular graph $G = (U, V, E)$ a $(k, \varepsilon)$-expander if for any $S \subset U$ with $|S| \leq k$ it holds that $|\mathcal{N}(S)| > (1- \varepsilon)d |S|$.
It is true that if $n \geq 2k \geq 2$ and $\varepsilon > 0$ there exists a $(k, \varepsilon)$-expander with $d = \mathcal{O}(\log(\frac{n}{k})/\varepsilon)$ and $m = \mathcal{O}(k \log(\frac{n}{k})/\varepsilon^2)$. This is a well-known result and supposedly it could be proven with Chernoff bounds, but I haven't been able to prove it or find sources with a proof.
I need some help in proving this last statement. If someone can shed some light, I would be very grateful!
Thanks!
