In this post, I’ll discuss the relationship between multi-flows and sparse cuts in graphs, bi-lipschitz embeddings into , and the weak differentiation of -valued mappings. It revolves around one of my favorite open questions in this area, the planar multi-flow conjecture.
Table of contents:
- The max-flow/min-cut theorem
- Multi-commodity flows and sparse cuts
- The planar multi-flow conjecture
- Bi-Lipschitz embeddings into
- The planar embedding conjecture
- Parallel geodesics and the slums of geometry
- Local rigidity and coarse differentiation
- Beyond planar graphs
The max-flow/min-cut theorem
Let be a finite, undirected graph, with a mapping assigning a capacity to every edge. If is the set of all paths from to , then an flow is a mapping which doesn’t overload the edges beyond their capacities: For every edge ,
The value of the flow F is the total amount of flow sent: . A cut in is a partition which we will usually write as . Naturally, one defines the capacity across by , where is the characteristic function of . 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 and any cut with and , we have . The classical max-flow/min-cut theorem says that in fact these upper bounds are achieved:
where the maximum is over all flows, and the minimum is over all cuts with and .
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 which requests that we send units of flow from to for every . 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
where the minimum is over pairs with . So if the value of the flow is , 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 , where is the total demand requested across , then for any valid flow . Unfortunately, it is no longer true in general that . (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 .
The planar multi-flow conjecture
It has been conjectured that there exists a universal constant such that if is a planar graph (i.e. can be drawn in the plane without edge crossings), there is a -approximate multi-commodity max-flow/min-cut theorem: For any choice of and , one has a
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 (discussed next). Perhaps the most compelling reason to to believe the conjecture is the beautiful result of Klein, Plotkin, and Rao which shows that for any planar instance where (this is called a uniform multi-flow instance).
It is relatively easy to see that we cannot take , as the following example of Okamura and Seymour shows.
In the example, the non-zero demands are for . It is easy to check that every cut has , but the value of the maximum flow is only , implying that . If we use the same pattern on the complete bipartite graph (instead of ), taking shows that we must have in (1). (Later a differentiation argument applied to a different family of graphs will show that we need in (1).)
For any graph , define as the smallest value such that (1) holds for every choice of capacities and demands on We will now see how is determined by the geometric properties of path metrics defined on
Bi-Lipschitz embeddings into
and (so if , then is an isometry up to scaling). The infimal value of for which is -bi-lipschitz is called the distortion of . Define as least distortion with which maps into .
We will now relate to the -distortion of the geometries that supports. Any set of non-negative weights on the edges of gives rise to a distance on defined by taking shortest-paths. Define to be the maximum of as ranges over all such weightings. (Strictly speaking, 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 , .
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 on . For any valid flow ,
To see why this holds, think of giving every edge a “length” of , and having a cross-sectional area of . 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 to requires volume at least . Observe that the bound (2) is a generalization of the cut upper bound when we define the pseudometric for some (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 is NP-hard, while maximizing can be done by linear programming. Thus we are trying to see how close we can get to the very complex object , by something which is efficiently computable.
The cut decomposition of . Now that we see why metrics come into the picture, let’s see how presents itself. Define a cut measure on a finite set as a mapping which satisfies for every .
Fact: Given , there exists a cut measure on such that for every . Conversely, for every cut measure , there exists a mapping for which the same equality holds.
Thus every -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 , and then integrate. As an example, consider these two isometric embeddings, presented via their cut measures (the graphs are unit-weighted):
In the 4-cycle, each cut has unit weight. The corresponding embedding into maps the four vertices to . 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 isometrically.)
Two comments are in order; first, when is finite, one can equivalently take the target space to be equipped with the norm (exercise: prove this using Caratheodory’s theorem). Thus one might ask why we would introduce a function space in the first place. One reason is that the dimension is irrelevant; a deeper reason is that when is infinite (in which case an appropriately stated version of the fact holds), is the proper setting (and not, e.g. ). 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 -embeddings, we can now state the planar multi-flow conjecture in its dual formulation.
Planar embedding conjecture: There exists a constant such that every shortest-path metric on a planar graph admits a -bi-lipschitz embedding into .
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 such that every Riemannian metric on the 2-sphere admits a -bi-lipschitz embedding into .
Recently, Indyk and Sidiropoulos proved that if it’s true for the 2-sphere, then it’s true for every compact surface of genus , where the constant depends on (as it must).
We can now state some known results in the dual setting of embeddings. Let be a planar graph, and let be a shortest-path metric on . The previously mentioned theorem of Klein, Plotkin, and Rao can be stated as follows: There exists a non-expansive mapping such that
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 be a face in some drawing of in the plane. Then there exists a non-expansive mapping such that 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 .
Finally, we mention the bound of Rao which shows that for planar metrics. A slightly more general version says that whenever the demand is supported on at most pairs, the flow/cut gap can be at most .
Read about the relationship with coarse differentiation after the jump.