CSE 525 (Spring 2019): HW #4

Due: Thurs, May 2nd, 11:59pm

Random tree embeddings

For the following problems, suppose that is a connected graph with unit edge weights, and let denote the shortest-path distance between and for .

(a) Hierarchical random partitions

In class, we showed the existence of random partitions that satisfy the following. For every , there is a random partition such that for all and so that for every , we have

with .

In order to construct tree embeddings, we will need a hierarchy of such random partitions, one for every value for . Moreover, we will need these random partitions to be hierarchical.

Say that a partition is a refinement of another partition if for every set , there is a set such that . Given two partitions and , we can take their common refinement which is the partition consisting of sets for all and . Note that is a refinement of both and .

Let be the random partition discussed above for . Your goal in this problem is to show that we can obtain another sequence of partitions that satisfy \eqref{eq:part} with for and , and such that is a refinement of for each . Think about using common refinements.

(b) Hiearchical partitions give random trees

Given the sequence of hierarchical partitions from the previous problem, let us define a random tree metric . There will be one vertex in the tree for every pair with and . We connect two nodes and by an edge of length if and and .

Construct also a map (here is the vertex set of ). We put (noting that consists solely of singleton clusters). Prove that is a tree, and is a random tree embedding (as defined in the lecture). Prove that the expected stretch is at most .

(c) Bonus question: LP rounding

Define the Sparsest Cut problem: Given a graph , find a subset to minimize the quantity

where denotes the complement of and is the set of edge running between and .

Consider the following continuous relaxation with variables for :

subject to the constraints , , and for all . This relaxation can be written as a linear programming problem.

First, show that this is indeed a relaxation (i.e., the optimal value over the choice of variables is at most the optimal value of the Sparsest Cut problem). Then show that you can use the tree embedding from part (2) to prove that the optimal Sparsest Cut value is at most a factor times more than the optimal value of the relaxation.

[Hint: The fractional solution is a metric. Embed this into a random tree metric, and then try to find a good cut in the tree. For finding cuts in the tree, it will suffice to look at cuts of the following form: For every edge of , removal of splits into two components.]

(d) Bonus question: Locality

From \eqref{eq:part} (using the probabilistic method), we can also conclude that there exists a partition with diameter bound , and such that at least half the pairs with are not separated by the partition.

Suppose we know something more about our space: Every -ball is small: . Can we improve this guarantee, maybe even to something which is independent of ? Use the symmetric version of the Lovász Local Lemma (see below) to prove that there exists a partition with diameter bound and such that at least half the pairs with are not separated by the partition.

Lovász Local Lemma, symmetric version: Suppose that are events in some probability space such that each is mutually independent of all but other events . If for every and If

then .