{"id":691,"date":"2014-04-21T17:00:55","date_gmt":"2014-04-21T21:00:55","guid":{"rendered":"http:\/\/matroidunion.org\/?p=691"},"modified":"2014-06-16T00:59:58","modified_gmt":"2014-06-16T04:59:58","slug":"seymours-1-flowing-conjecture-i","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=691","title":{"rendered":"Seymour’s 1-flowing conjecture I"},"content":{"rendered":"

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<\/em> if its members are pairwise edge-disjoint. An $s$-$t$ cut<\/em> 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:<\/p>\n

maximum size of a matching $\\leq$ minimum size of an $s$-$t$ cut.<\/p>\n

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<\/em> theorem was proved by Ford and Fulkerson [FF1956], and independently by Elias, Feinstein, and Shannon [EFS1956].<\/p>\n

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<\/em> will be a subset of $E$ that has non-empty intersection with each member of $\\mathcal{C}$. Then clearly<\/p>\n

maximum size of a matching $\\leq$ minimum size of a transversal<\/p>\n

and we will say that the system $(E,\\mathcal{C})$ packs<\/em> 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.<\/p>\n

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<\/p>\n

maximum size of a matching $\\leq$ minimum length of an $s$-$t$ path.<\/p>\n

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

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.<\/p>\n

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<\/em> of $x$. An $s$-$t$ flow<\/em> 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<\/em> 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,<\/p>\n

maximum value of an $s$-$t$ flow $\\leq$ minimum total capacity of an $s$-$t$ cut.<\/p>\n

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.<\/p>\n

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.<\/p>\n

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

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<\/em> [Sey1981]. If $M$ is $e$-flowing for every choice of $e$, then $M$ is $1$-flowing<\/em>. 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.<\/p>\n

[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.<\/p>\n

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

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

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

[Sey1981] P. D. Seymour, Matroids and multicommodity flows. European J. Combin. 2 (1981) 257-290.<\/p>\n","protected":false},"excerpt":{"rendered":"

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. … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-691","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/691","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=691"}],"version-history":[{"count":16,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/691\/revisions"}],"predecessor-version":[{"id":842,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/691\/revisions\/842"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=691"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=691"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=691"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}