In a well-known paper[ARV], Arora, Rao and Vazirani obtained an O(sqrt(log
n)) approximation to the Balanced Separator problem and Uniform Sparsest Cut.
At the heart of their result is a geometric statement about sets of points that
satisfy triangle inequalities, which also underlies subsequent work on
approximation algorithms and geometric embeddings.
In this note, we give an equivalent formulation of the Structure theorem in
[ARV] in terms of the expansion of large sets in geometric graphs on sets of
points satisfying triangle inequalities.