Monthly Archives: April 2014

Seymour’s 1-flowing conjecture I

Posted on by
Reply

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.

Matroid Computation with Sage: comparing matroids

Posted on by
3

I’m back with more on matroid computation in Sage. Previous installments are here, here, and here. As in the previous post, clicking the “Evaluate” buttons below will execute the code and return the answer. The various computations are again linked, so execute them in the right order.

Today we will look at various ways to ask (and answer) the question “Are these two matroids equal?” There are some subtle aspects to this, since we had to balance efficiency of the code and mathematical interpretation. The result is that we have various ways to compare matroids.

Isomorphism

Matroids $M$ and $N$ are isomorphic if there is a bijection $\phi: E(M) \to E(N)$ mapping bases to bases and nonbases to nonbases. In Sage, we check this as follows:

In other words, every matroid in Sage has a method .is_isomorphic() taking another matroid as input and returning True or False. Currently there is no way to extract the actual isomorphism (it is on our wish list), but if you guessed one, you can check its correctness:

We defined $\phi$ using a dictionary: for instance, phi['c'] equals 2. If you defined your map differently (e.g. as a function or a permutation), Sage will probably understand that too.

Equality

Matroids $M$ and $N$ are equal if $E(M) = E(N)$ and the identity map is an isomorphism. We can check for equality as follows:

==

The standard way to compare two objects in Sage is through the comparison operator ==. For instance,

When writing the matroid code, we chose to interpret the question M == N to mean “Is the internal representation of the matroid $M$ equal to the internal representation of $N$?” This is a very restricted view: the only time M == N will return True is if

  • $M$ and $N$ have the same internal data structure (i.e. both are of type BasisMatroid or both are of type LinearMatroid or …)
  • $M$ and $N$ are equal as matroids
  • The internal representations are equivalent (this is at the moment only relevant for linear matroids).

Let’s consider a few examples:

So only matroids $M_1$, $M_2$, and $M_4$ pass the equality test. This is because they are all linear matroids over the field $\mathrm{GF}(2)$, have the same ground set, and the matrices are projectively equivalent: one can be turned into the other using only row operations and column scaling. Matrix $M_3$ is isomorphic to $M_1$ but not equal; matroid $M_5$ is represented over a different field; matroid $M_6$ is represented by a list of bases, and matroid $M_7$ is represented by a list of “circuit closures”.

This notion of equality has consequences for programming. In Python, a set is a data structure containing at most one copy of each element.

So $S$ actually contains $M_3, M_5, M_6, M_7$, and one copy of $M_1, M_2, M_4$.

This means, unfortunately, that you cannot rely on Python’s default filtering tools for sets if you want only matroidally equal objects, or only isomorphic objects. But those equality tests are way more expensive computationally, whereas in many applications the matroids in a set will be of the same type anyway.

Inequivalent representations

As mentioned above, each instance of the LinearMatroid class is considered a represented matroid. There are specialized methods for testing projective equivalence and projective isomorphism. Recall that matroids are projectively equivalent (in Sage’s terminology, field-equivalent) if the representation matrices are equal up to row operations and column scaling. So below, matroids $M_1$ and $M_3$ are field-equivalent; matroids $M_1$ and $M_4$ are field-isomorphic; and matroid $M_2$ has an inequivalent representation:

I probably caused a lot of confusion, so feel free to ask questions in the comments below. Also, the documentation for the functions discussed above gives more explanations and examples.