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 ?


Try proving directly that with high probability, no set of size at most $n/2$ has a small edge neighborhood. See for example Ellis's writeup for the complete details.

Another possibility is to try and use a more sophisticated large deviation bound to analyze $|E(S,S')|$. For example, there are versions of Chernoff's bound for negatively dependent random variables, and there is Azuma's bound, which is a martingale version of Chernoff's bound. The classical example is concentration of the chromatic number, appearing in Chapter 7 of Alon & Spencer as well as many other places, such as Bukh's write-up.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.