Continuing from the previous post, we are going to prove the following result: let be a
-regular Cayley graph of an Abelian group,
be the normalized edge expansion of
,
be the value of the ARV semidefinite programming relaxation of sparsest cut on
(we will define it below), and
be the second smallest normalized Laplacian eigenvalue of
. Then we have
which, together with the fact that and
, implies the Buser inequality
The proof of (1), due to Shayan Oveis Gharan and myself, is very similar to the proof by Bauer et al. of (2).