A long time ago, I gave some background to the definition of a 1-flowing matroid. Assume $M$ is a matroid on the ground set $E$, and $e$ is an element in $E$. Take $c_{x}$ to be a non-negative integral capacity assigned to each element, $x$, in $E-e$. A flow is an assignment of a non-negative real, $f_{C}$, to each circuit, $C$, that contains $e$, with the constraint that if $x$ is in $E-e$, then the sum of $f_{C}$ over all circuits that contain $e$ and $x$ does not exceed $c_{x}$. We say that $M$ is $e$-flowing if, for every assignment of capacities, there is a flow whose value (sum over all circuits containing $e$) is equal to
\[\min\left\{\sum_{x\in C^{*}-e} c_{x}\mid C^{*}\ \text{is a cocircuit containing}\ e\right\}.\]
If $M$ is $e$-flowing for every $e$ in $E$, then $M$ is $1$-flowing.

We are motivated to study $1$-flowing matroids because problems that should really be intractable, magically become easy to solve when we consider such matroids. Consider the case of a graph with distinct vertices $s$ and $t$. We might ask for the largest number of edge-disjoint paths from $s$ to $t$. Now this resembles a difficult problem: we are asking to find a largest-possible pairwise-disjoint subfamily from a family of sets (the edge-sets of $s-t$ paths). Finding the maximum number of pairwise-disjoint sets is famously an NP-hard problem. However, as is well known, the problem of finding edge-disjoint $s-t$ paths can be solved using network-flow techniques by assigning a capacity of one to every edge. This really reflects the fact (discussed earlier) that graphic matroids are $1$-flowing. The fact that the maximum value of a flow through a network is equal to the minimum capacity of a cut gives enough structure to the problem to render it feasible.

In my most recent post, we can see another intimation that difficult problems may become tractable when dealing with $1$-flowing matroids. Let $M$ be a matroid on the ground set $E$, where $e$ is an element in $E$. We assign a real-valued variable $a_{x}$ to each element $x\in E-e$, and we insist that $a_{x}$ takes only non-negative values. In addition, for each circuit, $C$, that contains $e$, we require that the sum of variables, taken over all elements in $C-e$, must be at least one. Consider the set, $P$, of points in the Euclidean space $\mathbb{R}^{E-e}$ corresponding to assignments of values to variables such that these constraints are satisfied. Since $P$ is an intersection of half-spaces, it is a polyhedron. Now $M$ is $e$-flowing if and only if the $0$-dimensional extreme points (that is, the vertices) of $P$ have entirely integral coordinates. This means that integer programming problems associated with $P$ are in fact amenable to linear programming techniques. In other words, if there is a linear objective function which assigns a cost to each point in $P$, and we wish to find lowest-cost point in $P$ with integer coordinates, then we can relax the integrality constraint, since running the unconstrained linear program will return an integral point in any case. As integer programming is $NP$-hard, and linear progamming is solvable in polynomial time, this gives us some intuition as to why ostensibly difficult problems are easy for $1$-flowing matroids.

Proposition. The class of $1$-flowing matroids is closed under minors.

Proof. Let $M$ be a $1$-flowing matroid on the ground set $E$, and let $e$ be an element in $E$. Let $f$ be in $E-e$. We will show that $M\backslash f$ is $e$-flowing. Assume that each element $x\in E(M\backslash f)-e$ has been assigned a capacity $c_{x}$. We assign exactly the same capacities to these elements in $M$, and in addition we assign $f$ a capacity of $0$. Now every cocircuit of $M\backslash f$ is of the form $C^{*}-f$ where $C^{*}$ is a cocircuit of $M$, or is equal to a cocircuit of $M$. It follows that
\[
\min\left\{\sum_{x\in C^{*}-e} c_{x}\mid e\in C^{*}\in\mathcal{C}^{*}(M)\right\}\leq\min\left\{\sum_{x\in C^{*}-e} c_{x}\mid e\in C^{*}\in\mathcal{C}^{*}(M\backslash f)\right\}.
\]
If this is a strict inequality, then there is some cocircuit $C^{*}$ in $M$ that contains $e$, where the sum of capacities in $C^{*}-e$ is less than the minimum such sum in $M\backslash f$. Obviously $C^{*}$ is not a cocircuit of $M\backslash f$, so $f$ is in $\operatorname{cl}^{*}(C^{*})$. Thus some cocircuit $C^{*}_{0}$ of $M$ satisfies $f\in C^{*}_{0}\subseteq C^{*}\cup f$. But then $C^{*}_{0}-f$ is a cocircuit of $M\backslash f$ with total capacity at most the total capacity of $C^{*}$, a contradiction. Therefore the two minima are equal.

Since $M$ is $e$-flowing, there is a flow with value equal to these minima. We construct a flow for $M\backslash f$ with the same value by simply omitting all circuits that contains $e$ and $f$. This shows $M\backslash f$ is $e$-flowing.

Next we consider $M/f$. Assume that we assign the capacity $c_{x}$ to each $x$ in $E(M/f)-e$. Let $d$ be
\[
\min\left\{\sum_{x\in C^{*}-e} c_{x}\mid e\in C^{*}\in\mathcal{C}^{*}(M/f)\right\}.
\]
In $M$ we assign exactly the same capacities, and we also assign $f$ the capacity of $d$. It follows immediately that the minimum sum of capacities, taken over all cocircuits that contain $e$, is exactly the same in both matroids. Since $M$ is $1$-flowing, there is a flow whose value is equal to this minimum. For every circuit, $C$, in $M$ that contains $e$, there is a circuit, $\theta(C)$, of $M/f$ such that $\theta(C)\subseteq C$ and $e\in\theta(C)$. To construct a flow in $M/f$ we give each circuit $\theta(C)$ the sum of the values given to all pre-images of $C$ under $\theta$. Every other circuit receives a value of zero. This is enough to demonstrate that $M/f$ is $e$-flowing. The rest follows by easy induction. $\square$

Now we can hope to characterise the class of $1$-flowing matroids via its excluded minors. We might also note that the class is closed under duality. (This proof uses linear programming duality, and can be constructed from Theorem 1.17 in [Cor2001] and (3.1) in [Sey1977].) Thus the set of excluded minors will be closed under duality.

Let $M$ be isomorphic to $U_{2,4}$ and let $e$ be in $E$. We assign a capacity of one to the elements in $E-e$. Each cocircuit containing $e$ has a total capacity of two. Can we find a flow with this value? This would mean assigning values, $f_{1}$, $f_{2}$, and $f_{3}$, to the three circuits containing $e$, in such a way that $f_{1}+f_{2}+f_{3}=2$. However, the capacity constraints require that the sum of any two of $f_{1}$, $f_{2}$, and $f_{3}$ is at most one. A moment’s thought shows that this means $2(f_{1}+f_{2}+f_{3})\leq 3$, so there can be no solution to this system. Therefore $U_{2,4}$ is not $1$-flowing, and hence every $1$-flowing matroid is binary. The converse does not hold, as $AG(3,2)$ is not $1$-flowing (and is an excluded minor for the class). Seymour discovered two more excluded minors, $T_{11}$ and its dual. $T_{11}$ is the lift matroid of the even-cycle graph obtained from $K_{5}$ by making every edge negative.

Now we have arrived at the titular, and extremely lovely, conjecture by Seymour:

Conjecture (Seymour 1981). The set of excluded minors for the class of $1$-flowing matroids is $U_{2,4}$, $AG(3,2)$, $T_{11}$, and $T_{11}^{*}$.

[Cor2001] G. Cornuéjols, Combinatorial optimisation: Packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, 74. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001.

[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.

This post is another installment in my series on matroid computation in SageMath [1], with older posts here, here, here, and here. As always, clicking the “Evaluate” buttons below will execute the code and return the answer (or, in today’s post, draw the picture). The various computations are linked, so execute them in the right order.

Last summer, Jayant Apte was selected to participate in the Google Summer of Code program. During the summer he extended SageMath’s matroid capabilities in two major ways.

• Drawing geometric representations of rank-3 matroids
• A more efficient minor test for binary matroids

The first of these has been part of Sage for a while; the second is awaiting review but should be included fairly soon.

Let’s get started with everyone’s favorite matroid.

That was easy! We can deal with parallel elements too:

Loops are no problem either:

Note that we resort to a slightly different method of display for large parallel classes. The point in the geometric representation will receive a label that is not an element of the matroid, and below the diagram it will state that this label actually represents a parallel class of elements.

The examples above were chosen because the default positioning algorithm gives a decent picture. Unfortunately, that is not always the case:

In these instances, the options of the show() method come in handy. To get a full list, type M.show? in your own session of SageMath, and hit the key. This will bring up the help page of the method (assuming you defined $M$ to be a matroid in an earlier command). We will go through these options one by one.

This is not bad, but we don’t need a curved line to draw this diagram. The solution is to specify a different basis, whose elements will be placed at the corners of a triangle:

Trying different bases is not going to help the Pappus matroid too much. In that case, after inspecting, for instance, M.circuit_closures(), we can come up with custom coordinates for the points. To tell Sage that we’re doing this, we add the option pos_method=1.

A second example, just because:

Our final option today deals with betweenness. In projective geometry this is a meaningless concept, of course, but in a concrete diagram it can matter whether we draw a line from $a$ through $b$ to $c$ or from $b$ through $a$ to $c$. In SageMath, we can specify this through the line_orders option. An example should make this clear.

We specify the order on the line $\{d,e,f\}$:

A slightly less contrived example is provided by $\textrm{AG}(2,3)$.

I prefer a rotational symmetry to the curved lines:

It’s not perfect (I’d like the curved lines to protrude out of the square), but it’s in the ballpark.

Note: after you have drawn a matroid, the options for drawing so are saved. So next time,

will produce the same graphic.

There are many ways in which the drawing routines can be improved. Options like color, aspect ratio, letting the user decide how to handle parallel elements, and functionality like saving plot information when you save a matroid, adding “nice” plots to the built-in library of matroids, special plots for Dowling geometries, plots for rank-4 matroids, and the list goes on. Interested? There’s another Google Summer of Code coming up soon!

[1] SageMath is now the official name of the Sage Mathematical Software System.

Guest post by Thomas Savitsky

A $k$-polymatroid is a generalization of a matroid in which the rank of an element is allowed to exceed one, but cannot exceed $k$.

Definition 1.
Let $S$ be a finite set. Suppose $\rho : 2^S \to \mathbb{N}$ satisfies the following four conditions:

• if $X, Y \subseteq S$, then $\rho(X \cap Y) + \rho(X \cup Y) \le \rho(X) + \rho(Y)$
  (submodular);
• if $X \subseteq Y \subseteq S$, then $\rho(X) \le \rho(Y)$ (monotone);
• $\rho(\varnothing) = 0$ (normalized); and
• $\rho(\{x\}) \le k$ for all $x \in S$.

Then $(\rho, S)$ is a $k$-polymatroid with rank function $\rho$ and ground set $S$.

So a matroid is a $1$-polymatroid. Here are a few examples of $2$-polymatroids.

• If $(r_1, S)$, and $(r_2, S)$ are matroids, then $(r_1+r_2, S)$ is a $2$-polymatroid.
• If $G = (V, E)$ is a graph, one may define a $2$-polymatroid $(\rho, E)$, where
  $\rho(X)$ equals the number of vertices incident to $X$.
• Given an $m \times 2n$ matrix with entries in a field, one may define a representable $2$-polymatroid on $n$ elements by pairing up the columns in a obvious manner.

We became interested in $k$-polymatroids and thought it would be practical to have a catalog of the small ones at our disposal. We successfully adapted the canonical deletion
approach used by Mayhew and Royle (see [MR08]) to catalog matroids on nine elements to $2$-polymatroids. This first required developing a theory of single-element extensions of $k$-polymatroids. We then wrote code in the C programming language and interfaced with Brendan McKay’s nauty program and the igraph graph library. After a few days of execution time on a desktop computer, our program produced a catalog of all $2$-polymatroids, up to isomorphism, on at most seven elements.

By consulting our catalog, we produced Table 1, which lists the number of unlabeled $2$-polymatroids on the ground set $\{1, \ldots, n\}$ by rank.

Surprisingly, the number of $2$-polymatroids on seven elements is not unimodal in rank. In contrast, matroids are conjectured to be unimodal in rank, and the catalog of matroids with nine elements supports this. By the way, the symmetry in the columns in Table 1 is accounted for by a notion of duality for $2$-polymatroids.

Note that one can obtain the analogue of Table 1 for labeled $2$-polymatroids by computing the automorphism group of each $2$-polymatroid and then using the Orbit-Stabilizer relation. This allowed us to confirm the results of our enumeration through another means. By interpreting a $2$-polymatroid as a solution to a certain integer programming program, the number of labeled $2$-polymatroids can theoretically be computed by integer programming software. Fortunately, the software package SCIP was up to the task when $n \le 7$.

See [Sa14] for more details on all of the above.

Now recall that a matroid $M$ is paving if it contains no circuit of size less than $r(M)$. If both $M$ and $M^{*}$ are paving, then $M$ is sparse-paving. If $M$ is sparse-paving, then one can show that that every set of size less than $r(M)$ is independent and that the dependent $r(M)$-subsets are circuit-hyperplanes; furthermore, the symmetric difference of any two circuit-hyperplanes must be at least $4$. In fact, sparse-paving matroids are characterized by these properties.

It is conjectured that almost all matroids are sparse-paving.

The ideas in the remainder of this post were communicated to me by
Rudi Pendavingh.

We first mention the following background item. Let $S = \{e_1, e_2, \dots, e_n\} \cup \{f_1, f_2, \dots, f_n\}$ be a set of size $2n$. Suppose $(r, S)$ is a matroid. We will pair up the elements of $S$ to define a $2$-polymatroid as follows. Define $S’ = \big\{\{e_1, f_1\}, \{e_2, f_2\}, \dots, \{e_n, f_n\}\big\}$, and define $\rho : S’ \to \mathbb{N}$ by
$$\rho\big(\big\{\{e_{i_1}, f_{i_1}\}, \{e_{i_2}, f_{i_2}\}, \dots, \{e_{i_m}, f_{i_m}\}\big\}\big) = r(\{e_{i_1}, f_{i_1}, e_{i_2}, f_{i_2},\dots, e_{i_m}, f_{i_m}\}).$$
Then $(\rho, S’)$ is a $2$-polymatroid on $n$ elements with $\rho(S’) = r(S)$. Furthermore, every $2$-polymatroid on $n$ elements may be obtained in this manner from a matroid on $2n$ elements. See Section 44.6b of Schrijver’s Combinatorial Optimization or Theorem 11.1.9 of Oxley’s Matroid Theory for details.

Now assume that $r$ is a sparse-paving matroid. If $r(S)$ is odd, then $\rho$ does not detect any of the circuit-hyperplanes of $r$; namely,
\begin{equation*}
\rho(X) =
\begin{cases}
2|X| & \text{if} \ 2|X| < r(S),\\ r(S) & \text{if} \ 2|X| > r(S).\\
\end{cases}
\end{equation*}
To illustrate, all the rank-$7$ sparse-paving matroids on 14 elements map, in this manner, to a single rank-$7$ $2$-polymatroid on seven elements. However, if $r(S)$ is even, then the circuit-hyperplanes of $r$ are picked up by $\rho$. Perhaps this observation, combined with the conjecture that almost all matroids are sparse-paving, makes the non-unimodality of $2$-polymatroids appear more reasonable.

References

[MR08] Dillon Mayhew and Gordon F. Royle.
Matroids with nine elements.
J. Combin. Theory Ser. B, 98(2):415–431, 2008.
doi

[Sa14] Thomas J. Savitsky.
Enumeration of 2-polymatroids on up to seven elements.
SIAM J. Discrete Math., 28(4):1641–1650, 2014.
doi