Separated sets in unions of frames

In celebration of the recent resolution of the Kadison-Singer problem by Marcus, Spielman, and Srivastava, here is a question on isotropic point sets on which Kadison-Singer does not (seem to) shed any light. A positive resolution would likely have strong implications for the Sparsest Cut problem and SDP hierarchies. The question arose in discussions with Shayan Oveis Gharan, Prasad Raghavendra, and David Steurer.

Open Question: Do there exist constants \varepsilon, \delta > 0 such that for any k \in \mathbb N, the following holds? Let \mathcal B_1, \mathcal B_2, \ldots, \mathcal B_k \subseteq \mathbb R^k be a collection of k orthonormal bases and define W = \mathcal B_1 \cup \mathcal B_2 \cup \cdots \cup \mathcal B_k. Then there are subsets A,B \subseteq W with |A|,|B| \geq \varepsilon |W| and \min_{x \in A, y \in B} \|x-y\|_2 \geq \delta.

[Some additional notes: One piece of intuition for why the question should have a positive resolution is that these k orthonormal bases which together comprise at most k^2 vectors cannot possibly “fill” k-dimensional space in a way that achieves k-dimensional isoperimetry. One would seem to need \exp(O(k)) points for this.

One can state an equivalent question in terms of vertex expansion. Say that a graph G=(V,E) on k^2 vertices is a vertex expander if |N(S)| \geq 1.1 |S| for all subsets S \subseteq V with |S| \leq |V|/2. Here, N(S) denotes all the nodes that are in S or are adjacent to S. Then one can ask whether there exists a 1-1 mapping from V to \mathcal B_1 \cup \cdots \cup \mathcal B_k for some orthonormal bases \{\mathcal B_i\} such that the endpoints of every edge are mapped at most o(1) apart (as k \to \infty).]

Open question: PSD flows

This post is about a beautiful twist on flows that arises when studying (the dual) of the Sparsest Cut SDP.  These objects, which I’m going to call “PSD flows,” are rather poorly understood, and there are some very accessible open problems surrounding them.  Let’s begin with the definition of a normal flow:

Let G=(V,E) be a finite, undirected graph, and for every pair u,v \in V, let \mathcal P_{uv} be the set of all paths between u and v in G.  Let \mathcal P = \bigcup_{u,v \in V} \mathcal P_{uv}.  A flow in G is simply a mapping F : \mathcal P \to \mathbb R_{\geq 0}.  We define, for every edge (u,v) \in E, the congestion on (u,v) as

\displaystyle C_F(u,v) = \sum_{p \in \mathcal P: (u,v) \in p} F(p)

which is the total amount of flow going through (u,v).  Finally, for every u,v \in V, we define

F\displaystyle \lbrack u,v\rbrack = \sum_{p \in \mathcal P_{uv}} F(p)

as the total amount of flow sent from u to v.

Now, in the standard (all-pairs) maximum concurrent flow problem, the goal is to find a flow F which simultaneously sends D units of flow from every vertex to every other, while not putting more than one unit of flow through any edge, i.e.

\displaystyle \mathsf{mcf}(G) = \textrm{maximize } \left\{ \vphantom{\bigoplus} D : \forall u,v, F[u,v] \geq D \textrm{ and } \forall (u,v) \in E, C_F(u,v) \leq 1.\right\}

In order to define a PSD flow, it helps to write this in a slightly different way.  If we define the symmetric matrix

A_{u,v} = F[u,v] - D + {\bf 1}_{\{(u,v) \in E\}} - C_F(u,v)

then we have

Claim 1: \mathsf{mcf}(G) = \max \{ D : A_{u,v} \geq 0 \}.

To see that this is true, we can take a matrix with A_{u,v} \geq 0 for all u,v \in V and fix it one entry at a time so that F[u,v] \geq D and C_F(u,v) \leq 1, without decreasing the total demand satisfied by the flow.

For instance, if (u,v) \in E and C_F(u,v) > 1+\varepsilon, then it must be that F[u,v] > D+\varepsilon, so we can reroute \varepsilon units of flow going through the edge (u,v) to go along one of the extraneous flow paths which gives the excess F[u,v] > D + \varepsilon.  Similar arguments hold for the other cases (Exercise!).

PSD flows

So those are normal flows.  To define a PSD flow, we define for any symmetric matrix A, the Laplacian of A, which has diagonal entries L(A)_{i,i} = \sum_{j \neq i} A_{i,j} and off-diagonal entries L(A)_{i,j} = - A_{i,j}.  It is easy to check that

\displaystyle \langle x, L(A)\, x \rangle = \sum_{i,j} A_{i,j} (x_i-x_j)^2.

Hence if A_{u,v} \geq 0 for all u,v \in V, then certainly L(A) \succeq 0 (i.e. L(A) is positive semi-definite).  The PSD flow problem is precisely

\displaystyle \max \{ D : L(A) \succeq 0 \}

where A is defined as above.  Of course, now we are allowing A to have negative entries, which makes this optimization trickier to understand.  We allow the flow to undersatisfy some demand, and to overcongest some edges, but now the “error” matrix has to induce a PSD Laplacian.

Scaling down the capacities

Now, consider some \delta \in [0,1], and write

\displaystyle A_{u,v}^{(\delta)} = F[u,v] - D + \delta \cdot {\bf 1}_{(u,v) \in E} - C_F(u,v).

Requiring A_{u,v}^{(\delta)} \geq 0 for every u,v \in V simply induces a standard flow problem where each edge now has capacity \delta.  In the case of normal flows, because we can decouple the demand/congestion constraints as in Claim 1, we can easily relate \max \{ D : A_{u,v}^{(\delta)} \geq 0\,\forall u,v \in V\} to \max \{ D : A_{u,v} \geq 0\,\forall u,v \in V\} (the first is exactly \delta times the second, because we can just scale a normal flow down by \delta and now it satisfies the reduced edge capacities).

Question: Can we relate \max \{ D : L(A^{(\delta)}) \succeq 0 \} and \max \{ D : L(A) \succeq 0 \}?  More specifically, do they differ by some multiplicative constant depending only on \delta?

This is a basic question whose answer is actually of fundamental importance in understanding the Sparsest Cut SDP.  I asked this question in its primal form almost 4 years ago (see question 3.2 here).

Note that the answer is affirmative if we can decouple the demand/congestion constraints in the case of PSD flows.  In other words, let X_{u,v} = F[u,v] - D and let Y_{u,v} = {\bf 1}_{(u,v \in E)} - C_F(u,v).

Question: Can we relate \max \{ D : L(A) \succeq 0 \} to \max \{ D : L(X) \succeq 0 \textrm{ and } L(Y) \succeq 0 \}?

In the next post, I’ll discuss consequences of this question for constructing integrality gaps for the Sparsest Cut SDP.

The Cheeger-Alon-Milman inequality

[See comments on the post and the update below for the corrected argument.]

Recently, Luca posted on Cheeger’s inequality. Whenever I try to reconstruct the proof, I start with the coarea formula and then play around with Cauchy-Schwarz (essentially the way that Cheeger proved it). The proof below turned out to be a bit more complicated than I thought. Oh well…

Let G = (V,E) be a graph with maximum degree d_{\max} and n = |V| . Let’s work directly with the sparsity \displaystyle \alpha_G = \min_{S \subseteq V} \frac{e(S,\bar S)}{|S| |\bar S|} which is a bit nicer. Notice that \alpha_G n is within factor 2 of the Cheeger constant h_G . We start with a very natural lemma:

Coarea lemma: For any f : V \to \mathbb R , we have \sum_{ij \in E} |f(i)-f(j)| \geq \alpha_G \sum_{i,j \in V} |f(i)-f(j)| .

Proof: Let V_r = \{ i : f(i) \leq r \} , then we can write \sum_{ij \in E} |f(i)-f(j)| as the integral

\displaystyle \int_{-\infty}^{\infty} e(V_r, \bar V_r) dr \geq \alpha_G \int_{-\infty}^{\infty} |V_r| |\bar V_r|dr = \alpha_G \sum_{i,j \in V} |f(i)-f(j)|

Now a bit of spectral graph theory: L = D - A is the Laplacian of G , where D is the diagonal degree matrix and A is the adjacency matrix. The first eigenvalue is \lambda_1 = 0 and the first eigenvector is (1,1,\ldots,1) . If \phi : V \to \mathbb R is the second eigenvector, then the second eigenvalue can be written

\displaystyle \lambda_2 = \frac{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}{\sum_{i \in V} \phi(i)^2} \quad(1)

Given (1), it is natural to apply the coarea formula with f(i) = \phi(i)^2 and then play around.

Theorem: \displaystyle \lambda_2 \geq \frac{\alpha_G^2 n^2}{32 d_{\max}}

Proof: Unfortunately, if we try f(i) = \phi(i)^2 , it doesn’t quite work (think of the case when \phi takes some value v and -v equally often). Instead, let’s eliminate this case by setting \phi_0(i) = \max(m,\phi(i)) , where m = \mathrm{med}(\phi) . Now applying the coarea lemma with f(i) = \phi_0(i)^2 yields:

\displaystyle \alpha_G \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| \leq \sum_{ij \in E} |\phi_0(i)^2-\phi_0(j)^2|

\displaystyle = \sum_{ij \in E} |\phi_0(i)+\phi_0(j)||\phi_0(i)-\phi_0(j)| \leq \sqrt{\sum_{ij \in E} [\phi_0(i)+\phi_0(j)]^2} \sqrt{\sum_{ij \in E} |\phi_0(i)-\phi_0(j)|^2}

\displaystyle \leq \sqrt{2 d_{\max}} \sqrt{n m^2 + \sum_{i \in V} \phi(i)^2} \sqrt{\sum_{ij \in E} |\phi(i)-\phi(j)|^2}\quad\quad (2)

Notice that the same inequality holds for \phi_1(i) = \min(m, \phi(i)) . Also, observe that [the next inequality is wrong]

\displaystyle \sum_{i,j \in V} |\phi_0(i)^2-\phi_0(j)^2| + |\phi_1(i)^2-\phi_1(j)^2|

\displaystyle \geq \frac{n}{2} \sum_{i : \phi(i) \geq m} [\phi(i)-m]^2 + \frac{n}{2} \sum_{i : \phi(i) \leq m} [\phi(i)-m]^2

\displaystyle = \frac{n}{2} \sum_{i \in V} [\phi(i)-m]^2 = \frac{n}{2} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right] ,

where in the final line we have used the fact that \sum_{i \in V} \phi(i) = 0 since \phi is orthogonal to the first eigenvector.

So we can assume that \displaystyle \sum_{i,j \in V} |\phi_0(i)-\phi_0(j)|^2 \geq \frac{n}{4} \left[n m^2 +\sum_{i \in V} \phi(i)^2\right] . Plugging this into (2), rearranging, and using (1) yields the claim.

A better (and even correct) way to think about the argument [4-Nov-2015]

Define {\displaystyle h_G(S) = \frac{e(S,\bar S)}{|S|}} and for {f : V \rightarrow \mathbb R} define {\displaystyle  R_G(f)=\frac{\sum_{ij \in E} (f(i)-f(j))^2}{\sum_{i \in V} f(i)^2}} and {\textrm{supp}(f) = \{ i \in V : f(i) \neq 0 \}} .

Lemma (Cheeger with boundary conditions) For any {f : V \rightarrow \mathbb R} , there is a subset {S \subseteq \textrm{supp}(f)} with

\displaystyle  h_G(S) \leq \sqrt{2 d_{\max} R_G(f)}\,.

Proof: We may assume that {\textrm{supp}(f) \neq V} , else taking {S=V} finishes the argument. For {t \in [0,\infty)} , define a subset {S_t = \{ i \in V : f(i)^2 > t \}} . Observe that for every {t \geq 0} , the inclusion {S_t \subseteq \textrm{supp}(f)} holds by construction.

Then we have the estimate,

\displaystyle  \int_0^\infty |S_t|\,dt= \sum_{i \in V} f(i)^2

as well as,

\displaystyle  \begin{array}{rcl}  \int_0^\infty e(S_t,\overline{S_t})\,dt &=& \sum_{ij \in E} \left|f(u)^2-f(v)^2\right| \\ &= & \sum_{ij \in E} |f(i)-f(j)| \cdot |f(i)+f(j)| \\ &\leq & \sqrt{\sum_{ij \in E} (f(i)-f(j))^2} \sqrt{\sum_{ij \in E} (f(i)+f(j))^2} \\ &\leq & \sqrt{\sum_{ij \in E} (f(i)-f(j))^2} \sqrt{2 d_{\max} \sum_{i \in V} f(i)^2} \end{array}

Combining these two inequalities yields,

\displaystyle  \frac{\int_0^\infty e(S_t,\overline{S_t})\,dt}{ \int_0^\infty |S_t|\,dt} \leq \sqrt{2 d_{\max} R_G(f)},

implying there exists a {t \in [0,\infty]} for which {S_t} satisfies the statement of the lemma. \Box

Now to prove the Cheeger inequality, consider any map {\phi : V \rightarrow \mathbb R} with {\sum_{i \in V} \phi(i)=0} . Let {m} be some median of the set {\phi(V)} and consider the two functions {\phi_0(i)=\max(0,\phi(i)-m)} and {\phi_1(i)=\max(0,m-\phi(i))} . By the definition of {m} , applying the lemma to either {\phi_0} or {\phi_1} yields a set with {|S| \leq n/2} .

But we also have

\displaystyle  \sum_{i \in V} \phi_0(i)^2+\phi_1(i)^2 =\sum_{i \in V} (\phi(i)-m)^2 = nm^2 +\sum_{i \in V} \phi(i)^2 \geq \sum_{i \in V} \phi(i)^2\,,

where we have used the fact that {\sum_{i \in V} \phi(i)=0} . Thus we have at least one of {R_G(\phi_0) \leq 2 \,R_G(\phi)} or {R_G(\phi_1) \leq 2 \, R_G(\phi)} , completing the proof.

Planar multi-flows, L_1 embeddings, and differentiation

In this post, I’ll discuss the relationship between multi-flows and sparse cuts in graphs, bi-lipschitz embeddings into L_1, and the weak differentiation of L_1-valued mappings. It revolves around one of my favorite open questions in this area, the planar multi-flow conjecture.

Table of contents:

  1. The max-flow/min-cut theorem
  2. Multi-commodity flows and sparse cuts
  3. The planar multi-flow conjecture
  4. Bi-Lipschitz embeddings into L_1
  5. The planar embedding conjecture
  6. Parallel geodesics and the slums of geometry
  7. Local rigidity and coarse differentiation
  8. Beyond planar graphs

The max-flow/min-cut theorem

Let G=(V,E) be a finite, undirected graph, with a mapping \mathsf{cap} : E \to \mathbb R_+ assigning a capacity to every edge. If \mathcal P_{s,t} is the set of all paths from s to t, then an s\!-\!t flow is a mapping F : \mathcal P_{s,t} \to \mathbb R_+ which doesn’t overload the edges beyond their capacities: For every edge e \in E,

\displaystyle \sum_{\gamma \in \mathcal P_{s,t} : e \in \gamma} F(\gamma) \leq \mathsf{cap}(e).

The value of the flow F is the total amount of flow sent: \mathsf{val}(F) = \sum_{\gamma \in \mathcal P_{s,t}} F(\gamma). A cut in G is a partition V = S \cup \bar S which we will usually write as (S, \bar S). Naturally, one defines the capacity across (S, \bar S) by \mathsf{cap}(S,\bar S) = \sum_{xy \in E} \mathsf{cap}(x,y) |\mathbf{1}_S(x)-\mathbf{1}_S(y)|, where \mathbf{1}_S is the characteristic function of S. Since one can only send as much flow across a cut as there is capacity to support it, it is easy to see that for any valid flow F and any cut (S, \bar S) with s \in S and t \in \bar S, we have \mathsf{val}(F) \leq \mathsf{cap}(S, \bar S). The classical max-flow/min-cut theorem says that in fact these upper bounds are achieved:

\max_{F} \mathsf{val}(F)=\min_{(S, \bar S)} \mathsf{cap}(S, \bar S)

where the maximum is over all s\!-\! t flows, and the minimum is over all cuts (S, \bar S) with s \in S and t \in \bar S.

Multi-commodity flows and sparse cuts

We will presently be interested in multi-commodity flows (multi-flows for short), where we are given a demand function \mathsf{dem} : V \times V \to \mathbb R_+ which requests that we send \mathsf{dem}(x,y) units of flow from x to y for every x,y \in V. In this case, we’ll write the value of a valid flow (i.e. one which doesn’t try to send more total flow than an edge can carry) as

\displaystyle \mathsf{val}(F) = \min_{x,y \in V} \frac{\sum_{\gamma \in \mathcal P_{x,y}} F(\gamma)}{\mathsf{dem}(x,y)}

where the minimum is over pairs with \mathsf{dem}(x,y) \neq 0. So if the value of the flow is \frac12, it means that every pair gets at least half the flow it requested (well, demanded).

Again, cuts give a natural obstruction to flows. If we define \Phi(S, \bar S) = \displaystyle \frac{\mathsf{cap}(S, \bar S)}{\mathsf{dem}(S, \bar S)}, where \mathsf{dem}(S, \bar S) = \sum_{x,y \in V} \mathsf{dem}(x,y) |\mathbf{1}_S(x)-\mathbf{1}_S(y)| is the total demand requested across (S, \bar S), then \mathsf{val}(F) \leq \Phi(S, \bar S) for any valid flow F. Unfortunately, it is no longer true in general that \max_F \mathsf{val}(F) = \min_{(S, \bar S)} \Phi(S). (It is true as long as the demand is supported on a set of size at most 4, while it stops being true in general when the demand is supported on a set of size 5 or larger.)

In fact, the gap between the two can be arbitrarily large, as witnessed by expander graphs (this rather fruitful connection will be discussed in a future post). For now, we’ll concentrate on a setting where the gap is conjectured to be at most O(1).

The planar multi-flow conjecture

It has been conjectured that there exists a universal constant C \geq 1 such that if G=(V,E) is a planar graph (i.e. can be drawn in the plane without edge crossings), there is a C-approximate multi-commodity max-flow/min-cut theorem: For any choice of \mathsf{dem} and \mathsf{cap}, one has a

\displaystyle \frac{1}{C} \min_{(S, \bar S)} \Phi(S, \bar S) \leq \max_F \mathsf{val}(F) \leq \min_{(S, \bar S)} \Phi(S, \bar S) (1)

The conjecture first appeared in print here, but was tossed around since the publications of Linial, London, and Rabinovich and Aumann and Rabani, which recast these multi-flow/cut gaps as questions about bi-lipschitz mappings into L_1 (discussed next). Perhaps the most compelling reason to to believe the conjecture is the beautiful result of Klein, Plotkin, and Rao which shows that C = O(1) for any planar instance where \mathsf{dem}(x,y) = 1\,\,\forall x,y \in V (this is called a uniform multi-flow instance).

It is relatively easy to see that we cannot take C=1, as the following example of Okamura and Seymour shows.

Okamura-Seymour graph

In the example, the non-zero demands are \mathsf{dem}(s_i,t_i) = 1 for i \in \{1,2,3,4\}. It is easy to check that every cut has \Phi(S,\bar S) \geq 1, but the value of the maximum flow is only 3/4, implying that C \geq 4/3. If we use the same pattern on the complete bipartite graph K_{2,n} (instead of K_{2,3}), taking n \to \infty shows that we must have C \geq 3/2 in (1). (Later a differentiation argument applied to a different family of graphs will show that we need C \geq 2 in (1).)

For any graph G, define \mathsf{gap}(G) as the smallest value C such that (1) holds for every choice of capacities and demands on G. We will now see how \mathsf{gap}(G) is determined by the geometric properties of path metrics defined on G.

Bi-Lipschitz embeddings into L_1

Consider a metric space (X,d), and the space of absolutely integrable functions L_1 = L_1([0,1]), equipped with the \|\cdot\|_1 norm. A mapping f : X \to L_1 is said to be C-bi-lipschitz if there exist constants A,B > 0 such that for all x,y \in X,

\frac{1}{B} d(x,y) \leq \|f(x)-f(y)\|_1 \leq A\,d(x,y)

and C = A \cdot B (so if C=1, then f is an isometry up to scaling). The infimal value of C for which f is C-bi-lipschitz is called the distortion of f. Define c_1(X) as least distortion with which (X,d) maps into L_1.

We will now relate \mathsf{gap}(G) to the L_1-distortion of the geometries that G supports. Any set of non-negative weights w : E \to \mathbb R_+ on the edges of G gives rise to a distance \mathrm{dist}_w on V defined by taking shortest-paths. Define c_1(G) to be the maximum of c_1(V, \mathrm{dist}_w) as w ranges over all such weightings. (Strictly speaking, \mathrm{dist}_w is only a pseudometric.)

Here is the beautiful connection referred to previously (see this for a complete proof).

Theorem (Linial-London-Rabinovich, Aumann-Rabani): For any graph G, \mathsf{gap}(G) = c_1(G).

Metric obstructions. To give an idea of why the theorem is true, we mention two facts. It is rather obvious how a cut obstructs a flow. A more general type of obstruction is given by a metric \mathrm{dist} on V. For any valid flow F,

\displaystyle \mathsf{val}(F) \leq \frac{\sum_{xy \in E} \mathsf{cap}(x,y)\,\mathrm{dist}(x,y)}{\sum_{x,y \in V} \mathsf{dem}(x,y)\,\mathrm{dist}(x,y)} (2)

To see why this holds, think of giving every edge (x,y) \in E a “length” of \mathrm{dist}(x,y), and having a cross-sectional area of \mathsf{cap}(x,y). Then the numerator in (2) is precisely the “volume” of the network, while the denominator is the total “volume” required to satisfy all the demands: By the triangle inequality, sending one unit of flow from x to y requires volume at least \mathrm{dist}(x,y). Observe that the bound (2) is a generalization of the cut upper bound when we define the pseudometric \mathrm{dist}(x,y) = |\mathbf{1}_S(x)-\mathbf{1}_S(y)| for some S \subseteq V (this is called a cut pseudometric).

It turns out (by linear programming duality) that in fact metrics are the correct dual objects to flows, and maximizing the left hand side of (2) over valid flows, and minimizing the right-hand side over metrics yields equality (it is also easy to see that the minimal metric is a shortest-path metric). One might ask why one continues to study cuts if they are the “wrong” dual objects. I hope to address this extensively in future posts, but the basic idea is to flip the correspondence around: minimizing \Phi(S,\bar S) is NP-hard, while maximizing \mathsf{val}(F) can be done by linear programming. Thus we are trying to see how close we can get to the very complex object \Phi, by something which is efficiently computable.

The cut decomposition of L_1. Now that we see why metrics come into the picture, let’s see how L_1 presents itself. Define a cut measure on a finite set X as a mapping \mu : 2^X \to \mathbb R_+ which satisfies \mu(S) = \mu(\bar S) for every S \subseteq X.

Fact: Given F : X \to L_1, there exists a cut measure \mu on X such that \|F(x)-F(y)\|_1 = \sum_S \mu(S) |\mathbf{1}_S(x)-\mathbf{1}_S(y)| for every x,y \in X. Conversely, for every cut measure \mu, there exists a mapping F : X \to L_1 for which the same equality holds.

Thus every L_1-distance on a finite set is precisely a weighted sum of cut pseudometrics (and, of course, cuts are where this story began). Proving the fact is straightforward; first check that it holds for F : X \to \mathbb R, and then integrate. As an example, consider these two isometric embeddings, presented via their cut measures (the graphs are unit-weighted):

4-cycle 5-cycle embedding

In the 4-cycle, each cut has unit weight. The corresponding embedding into (\mathbb R^2, \|\cdot\|_1) maps the four vertices to \{(0,0),(0,1),(1,0),(1,1)\}. In the second example, the dashed cuts have weight 1/2, and the dotted cut has weight 1. (Exercise: Verify that every tree embeds into L_1 isometrically.)

Two comments are in order; first, when X is finite, one can equivalently take the target space to be \mathbb R^{|X| \choose 2} equipped with the \|\cdot\|_1 norm (exercise: prove this using Caratheodory’s theorem). Thus one might ask why we would introduce a function space L_1 in the first place. One reason is that the dimension is irrelevant; a deeper reason is that when X is infinite (in which case an appropriately stated version of the fact holds), L_1 is the proper setting (and not, e.g. \ell_1). This arises, for instance, in arguments involving ultralimits in the passage between the finite and infinite settings.

The planar embedding conjecture

Using the connection with L_1-embeddings, we can now state the planar multi-flow conjecture in its dual formulation.

Planar embedding conjecture: There exists a constant C \geq 1 such that every shortest-path metric on a planar graph G=(V,E) admits a C-bi-lipschitz embedding into L_1.

By a relatively simple approximation argument in one direction, and a compactness argument in the other, one has the following equivalent conjecture.

Riemannian version: There exists a constant C \geq 1 such that every Riemannian metric on the 2-sphere admits a C-bi-lipschitz embedding into L_1.

Recently, Indyk and Sidiropoulos proved that if it’s true for the 2-sphere, then it’s true for every compact surface of genus g \geq 1, where the constant C depends on g (as it must).

We can now state some known results in the dual setting of embeddings. Let G=(V,E) be a planar graph, and let \mathrm{dist} be a shortest-path metric on V. The previously mentioned theorem of Klein, Plotkin, and Rao can be stated as follows: There exists a non-expansive mapping f : V \to \mathbb R such that

O(1) \sum_{x,y \in V} |f(x)-f(y)| \geq \sum_{x,y \in V} \mathrm{dist}(x,y).

In Gromov’s language, the observable diameter of planar graph metrics is almost as large as possible (i.e. no forced concentration of Lispchitz mappings).

A classical theorem of Okamura and Seymour is stated in the embedding setting as: Let F \subseteq V be a face in some drawing of G in the plane. Then there exists a non-expansive mapping f : V \to L_1 such that f|_F is an isometry. In the flow setting, this says that if the demand function is supported on the pairs belonging to a single face, then (1) holds with C=1.

Finally, we mention the bound of Rao which shows that c_1(V,d) = O(\sqrt{\log |V|}) for planar metrics. A slightly more general version says that whenever the demand is supported on at most k pairs, the flow/cut gap can be at most O(\sqrt{\log k}).

Read about the relationship with coarse differentiation after the jump.

Continue reading