1 Last TheoryLunch Meeting at Weizmann Institute of Science

For those of you who don’t know, this blog originated from my lunch meetings with my friends at Weizmann Institute of Science during my Master studies. As all good things comes to an end, also did my time at Weizmann, and last week our lunch group gathered for the last time. This post presents the topic discussed on that meeting.
I want to thank my good friends, Yosef Pogrow and Ron Shiff, for the great time we had and for all the enriching lunch meetings (also those which didn’t include theory). Without you guys, this blog would not have been created, I wish you both best of luck ahead!
This post, by the way, contains some results from the research of Yosef Pogrow (who also presented most of the meetings).

2 Min-Cuts in a Graph

This post deals with undirected, weighted graphs and cuts on them. We denote by the graph equipped with a weight function on its edges. A cut in this graph is a partition of its vertices to where . For simplicity, we will only mention one of the parts in the partition, usually . Note that it doesn’t matter whether we refer to the first part in the partition , or to the second part , because both parts define the same cut.
The value of the cut is defined as
A min -cut for a pair is a cut defined by such that note that it is possible that several cuts will satisfy the definition above, but for our purposes they are equivalent (since they all have the same value).
Before diving into the theorem about cut equivalent trees, we setup the following notation. For a given tree and any edge , removing that edge from the tree breaks it down into two connected components, one that contains , and another one that contains . Denote the component containing as , and then the other component is exactly . Since the only path connecting and was the removed edge, then is actually the min -cut in (the same is true for since it defines the same cut).
A simple fact about trees is, that for any tree and vertices inside it, the min -cut is given by where is the edge with minimum weight along the path that connects and . Since any vertices tree has exactly edges, there are at most unique values of min-cuts that the tree can yield.
Cut-Equivalent Trees [Gomory and Hu, 1961]. For any weighted undirected graph there is a weighted tree on the same set of vertices such that:
(a) for any , the value of the min -cut in is equal the value of the min -cut in (with respect to their respective weight functions), and
(b) for any edge , Such trees are known as Cut-Equivalent trees (also known as GH-trees).
The proof is omitted from this post, and we move to discuss a nice implication of that theorem: it puts a limit on the number of different min-cut values that a graph can have. Since there are different pairs in a graph there can be potentially unique min-cut values, however, the theorem says that any value of a min-cut in is being represented by a (possibly different) min-cut in , and there are at most min-cut values in , then has at most unique min-cut values.

3 General Cuts in a Graph

Until now, we talked about minimum cuts. The theorem above state that for any graph , there is a cut-equivalent tree that can tell us much about all the minimum cuts in . It can tell us all the possible min-cut values that can have, moreover, for any min-cut value , there is a very easy way to find a cut in that have this exact value. All we need to do is to find an edge in the tree that have weight , suppose that edge is , and the desired cut in is given by .
One interesting question to ask is, what cut-equivalent trees can tell us about “general” cuts? The answer is given in the following theorem.
[Krauthgamer and Pogrow, 2017]. Let be a weighted undirected graph with vertices, and let be a cut-equivalent tree of . Then for any
We start with the left-hand side. Recall that the value of a cut is the sum of weights of all the “crossing edges”, meaning, edges which have endpoints in both parts of the partition. Then, combined with the second property of the tree, and the fact that for any edge , we get so it is suffice to show that any crossing edge in the sum of the original graph , contributes also to a sum of for some tree-edge such that . So fix some crossing edge ( ) from the original graph, and consider the unique path connecting and over the tree. Since we starting the path with a vertex from and ending with a vertex in , there must be an edge along the path such that and . That edge separates from in the tree, so and . Since then it contributes to , which is what we wanted to prove.
We proceed to show the second inequality. For each in the sum of , we know that since the weight of the tree-edge is equal to the min -cut in , thus in particular smaller or equal to the value of the cut (which also separates from but might not be of minimum weight). The inequality follows by summing over all the crossing edges in over , which is at most edges.

4 The Inequalities are Tight

We conclude this post with examples for cases in which one of the inequalities became an equality.
For the first inequality, take any graph and a corresponding cut equivalent tree . Fix an arbitrary tree-edge . The cut is the min -cut in and by the first property of the tree .
For the second inequality, consider the complete graph on vertices with all its edges weighted . Its cut-equivalent tree must be a star in which every edge weighed . See example of an eight vertices star in the figure below (taken from Wikipedia).
figure star_graph.png
Suppose the vertex in the center of the star is . The cut has weight of over , however, it has weight in the star which is exactly .