A uniform sparsest cut is a sparsest cut with demand 1 between each pair of distinct vertices. For a finite undirected graph 
with vertex
set 
of size 
and nonnegative capacities 
, its optimum is
 |
The denominator counts the unordered pairs separated by the cut. An approximation factor 
means returning a cut with ratio at most 
(Rothvoss 2016). For the unweighted complete
graph 
,
every nontrivial cut has ratio
1.
