Seymour’s 1-flowing conjecture I

Let $G$ be a graph with distinct vertices $s$ and $t$, and let $\mathcal{C}$ be the family of paths from $s$ to $t$. Let us say that a subfamily of $\mathcal{C}$ is a matching if its members are pairwise edge-disjoint. An $s$-$t$ cut is a subset of edges in $G$ with the property that removing that set of edges destroys every path from $s$ to $t$. From this definition, we can clearly see that an $s$-$t$ cut contains an edge from each path in any matching. Thus we conclude:

maximum size of a matching $\leq$ minimum size of an $s$-$t$ cut.

It is a very well-known result, but no less lovely for it, that this inequality is actually an equality. That is, the minimum size of an $s$-$t$ cut is exactly equal to the maximum size of a matching. This classic result, known as the max-flow min-cut theorem was proved by Ford and Fulkerson [FF1956], and independently by Elias, Feinstein, and Shannon [EFS1956].

Let us consider this phenomenon in a more general context. Let $E$ be a finite set, and let $\mathcal{C}$ be a family of subsets. A matching will be a subfamily of $\mathcal{C}$ consisting of pairwise disjoint subsets of $E$. A transversal will be a subset of $E$ that has non-empty intersection with each member of $\mathcal{C}$. Then clearly

maximum size of a matching $\leq$ minimum size of a transversal

and we will say that the system $(E,\mathcal{C})$ packs if the two quantities are equal. This terminology was introduced by Seymour [Sey1977]. Thus, if $E$ is the edge set of $G$, and $\mathcal{C}$ is the family of edge-sets of $s$-$t$ paths, then $(E,\mathcal{C})$ packs.

Let’s look at another, dual, example. Again, $G$ is a graph, and $s$ and $t$ are distinct vertices. Let $\mathcal{C}^{*}$ be the family of $s$-$t$ cuts. If we consider an arbitrary matching in $\mathcal{C}^{*}$, that is, a collection of pairwise disjoint $s$-$t$ cuts, then we can clearly see that an $s$-$t$ path must intersect each cut in the matching, so

maximum size of a matching $\leq$ minimum length of an $s$-$t$ path.

Fulkerson observed that this inequality is also an equality, so $(E,\mathcal{C}^{*})$ packs [Ful1968]. This is sometimes called the min-potential max-work theorem (or at least a special case thereof).

Both of these examples can be seen in a matroidal light. We add the edge $e=st$ to $G$. Call the resulting graph $G^{+}$, and consider $M(G^{+})$. Then $C$ is the edge-set of an $s$-$t$ path if and only if $C\cup e$ is a circuit of $M(G^{+})$, and $C^{*}$ is the edge-set of an $s$-$t$ cut if and only if $C^{*}\cup e$ is a cocircuit of $M(G^{+})$. From this we can deduce that if $M$ is a graphic or cographic matroid, with ground set $E$, and $e\in E$, then the set systems $(E-e,\{C-e\mid C\ \text{is a circuit of}\ M\ \text{and}\ e\in C\})$ and $(E-e,\{C^{*}-e\mid C^{*}\ \text{is a cocircuit of}\ M\ \text{and}\ e\in C^{*}\})$ both pack.

We can do more, and consider weighted versions of these problems. Let us illustrate by assuming that every edge, $x$, in $G$ is assigned a positive integer, $c_{x}$, the capacity of $x$. An $s$-$t$ flow is an assignment that gives, to each $s$-$t$ path, $P$, a value, $f_{P}$, from $\mathbb{R}^{+}\cup\{0\}$. We insist that, for every edge, $x$, the total $\sum f_{P}$ does not exceed $c_{x}$ (here the sum is taken over all $s$-$t$ paths that contain $x$). We can think of a flow as a movement of liquid through the network, from $s$ to $t$, in such a way that the total amount of liquid flowing through any edge does not exceed the capacity of that edge. The value of the flow is the total $\sum f_{P}$, summed over all $s$-$t$ paths. Clearly, if we cut a swath through the network, disconnecting $s$ and $t$, the volume of liquid that flows onto the floor will be no greater than the total capacity of the edges we have just cut. Put less floridly,

maximum value of an $s$-$t$ flow $\leq$ minimum total capacity of an $s$-$t$ cut.

The max-flow min-cut theorem says that this inequality is an equality for any choice of capacities. What is more, there is a flow meeting this bound that assigns an integer value to every $s$-$t$ path, so we can recover our earlier version of the theorem by assigning a capacity of $1$ to every edge.

This idea of weighting can also be translated into matroidal language. Let us say that $M$ is a matroid with ground set $E$, and $e$ is in $E$. Every element $x\in E-e$ is assigned a capacity, $c_{x}$, from $\mathbb{Z}^{+}$. A flow is an assignment that gives a non-negative real value, $f_{C}$, to each circuit, $C$, of $M$ that contains $e$. We insist that, for every element, $x\in E-e$, the total $\sum f_{C}$ does not exceed $c_{x}$ (the sum is taken over all circuits of $M$ that contain $e$ and $x$). The value of a flow is the sum $\sum f_{C}$ over all circuits that contain $e$. Exercise: prove that the following inequality holds.

maximum value of a flow $\leq$ min $\left\{\sum_{x\in C^{*}-e}c_{x}\right\}$

where the minimum is taken over all cocircuits, $C^{*}$, that contain $e$. What can we say about $M$ if this inequality is an equality for all choices of capacities? The least we can do is give it a name, so we follow Seymour, and say $M$ is $e$-flowing [Sey1981]. If $M$ is $e$-flowing for every choice of $e$, then $M$ is $1$-flowing. The max-flow min-cut and min-potential max-work theorems imply that graphic and cographic matroids are $1$-flowing, but are there other $1$-flowing matroids, and if so, can we characterise them? This characterisation is the subject of a beautiful open problem, due to Seymour, but that will have to wait for my next post.

[EFS1956] P. Elias, A. Feinstein, and C. Shannon, A note on the maximum flow through a network. IEEE Transactions on Information Theory, 2 (1956) 117-119.

[FF1956] L. R. Ford and D. R. Fulkerson, Maximal flow through a network. Canad. J. Math. 8 (1956) 399-404.

[Ful1968] D. R. Fulkerson, Networks, frames, blocking systems. 1968 Mathematics of the Decision Sciences, Part 1 (Seminar, Stanford, Calif., 1967) 303-334.

[Sey1977] P. D. Seymour, The matroids with the max-flow min-cut property. J. Combinatorial Theory Ser. B 23 (1977) 189-222.

[Sey1981] P. D. Seymour, Matroids and multicommodity flows. European J. Combin. 2 (1981) 257-290.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.