*In which we prove that there are -point metric spaces that cannot be embedded into L1 with distortion , and we see further applications of Leighton-Rao type relaxations and of the use of metric embeddings as rounding schemes.*

**1. Tightness of the Analysis of the Leighton-Rao Relaxation **

If and are metric spaces, we say that a mapping is an *embedding of into with distortion at most * if there are parameters , with such that, for every , we have

The metric space with distance is denoted by , and the metric space with distance is denoted by . In the past lecture we proved the following result.

Theorem 1 (Bourgain)There is an absolute constant such that every finite metric space embeds into with distortion at most , where .

If we solve the Leighton-Rao linear programming relaxation to approximate the sparsest cut of a graph , and we let be an optimal solution, we note that, if we weigh each edge by , and then compute shortest paths in this weighted graph, then, for every two vertices , the distance is precisely the length of the shortest path from to . In particular, if we are using the Leighton-Rao relaxation in order to approximate the sparsest cut in a given *planar* graph, for example, then the solution that we need to round is not an arbitrary metric space, but it is the shortest path metric of a weighted planar graph. It is conjectured that, in this case, the Leighton-Rao relaxation could deliver a constant-factor approximation.

Is there an absolute constant such that every metric space constructed as the shortest-path metric over the vertices of a planar graph can be embedded into with distortion at most , where ?

So far, it is known that -*outerplanar* graphs, for constant , embed in with constant distortion.

This is just an example of a large family of questions that can be asked about the embeddability of various types of metric spaces into each other.

For general finite metric spaces, the logarithmic distortion of Bougain’s theorem is best possible.

In order to prove the optimality of Bourgain’s theorem, we will state without proof the existence of constant degree families of expanders. In a later part of the course we will prove their existence and give efficient constructions.

Theorem 2 (Existence of Expanders)There are absolute constants and such that, for infinitely many , there is an -vertex -regular graph such that .

On such graphs, the Leighton-Rao relaxation is , showing that our proof that is tight.

For every two vertices , define as the length of (that is, the number of edges in) a shortest path from to in .

Then

Because each graph is -regular, it follows that for every vertex there are vertices at distance from . In particular, at least half of the vertices have distance from , where , which implies that

Recall that

and so

even though

Note that we have also shown that every embedding of the shortest-path metric on into requires distortion , and so we have proved the tightness of Bourgain’s theorem.

**2. The Non-Uniform Sparsest Cut Problem **

In the *non-uniform sparsest cut* problem, we are given two graphs and over the same set of vertices, and we want to find a non-trivial cut of the vertex set that minimizes the *non-uniformity sparsity*

The non-uniformity sparsity of an optimal solution is denoted by . Note that the standard sparsest cut problem corresponds to taking to be a clique.

The graph is called the *capacity* graph and the graph is called the *demand* graph. This terminology will become more clear when we discuss the dual of the Leighton-Rao relaxation of sparsest cut at a later point. The intuition for the problem is that specifies which pairs of nodes we would like to see disconnected in , and our goal is to find a set of edges to remove such that their number is small compared to the number of pairs of elements of that are disconnected by their removal.

We can easily adapt the theory that we have developed for sparsest cut to the non-uniform version of the problem. In particular, we can define a Leighton-Rao relaxation

where is the adjacency matrix of and is the adjacency matrix of .

We can also define the special case of the Leighton-Rao relaxation in which the distance function is an embedding:

Exactly the same proof that established can be used to prove

And, finally, Bourgain’s embedding can be used to map a solution of the Leighton-Rao relaxation to an solution, with increase in the cost function, and then the solution can be mapped to a cut with no loss, leading to the relation

for every two graphs over the same set of vertices.

Prof. Trevisan, the sparsest cut problem seems to be “easier” in d-regular graph. Is the problem still NP-hard in d-regular graph?