If a (n,d) random graph is a n-vertex graph defined as :
Choose d random permutations $\pi_1 \ldots \pi_d $, from [n] to [n]. Take edge (u,v) if $v = \pi_i(u)$ for some i. I am trying to prove that, for every n and $d \geq 2$, a (n,d) random graph is a (n,2d,1/10) edge expander with probability 1 - o(1).
For a given S such that $|S| \leq n/2$, I have found the expected value of the number of edges |E(S,S')| between S and V\S. But since this random variable is the addition of random variables which are not independent, I cannot apply the Chernoff bound to say that, the probability of |E(S,S')| being far from its expected value is low.
Is there any other way to prove this ?