*In which we introduce the sparsest cut problem and the Leighton-Rao relaxation.*

**1. The Uniform Sparsest Cut problem, Edge Expansion and **

Let be an undirected graph with vertices.

We define the uniform sparsity of a cut as

(we will omit the subscript when clear from the context) and the uniform sparsest cut of a graph is

In -regular graphs, approximating the uniform sparsest cut is equivalent (up to a factor of 2 in the approximation) to approximating the edge expansion, because, for every cut , we have

and, noting that, for every, ,

we have, for every ,

and so

It will be instructive to see that, in -regular graphs, is a relaxation of , a fact that gives an alternative proof of the easy direction of Cheeger’s inequalities.

Continue reading →