Seymour’s 1-flowing conjecture III

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.

Matroids and graphs in Princeton

All the contributors to this blog have been in Princeton, New Jersey within the last few weeks for the 2014 International Workshop on Structure in Graphs and Matroids. This meeting is a descendant of three very successful workshops run by Bert Gerards in Sittard and Maastricht between 2008 and 2012. Although the location has shifted from the Netherlands to the US, a Dutch connection remains, since the 2014 workshop was organised by Rudi Pendavingh and Stefan van Zwam. They both deserve a vote of thanks, for doing a great job and for continuing the tradition; the biennial meeting has become one of the most important fixtures for people interested in the structural theory of matroids and graphs.

In this type of post, I would usually make note of talks that were relevant to the contents of this blog, as well as talks that I found particularly interesting or attractive. That rule is pretty much useless in this case. For obvious reasons, all the talks had connections to matroid theory, and a large number of talks were high-quality presentations about high-quality results. Judging by a number of conversations I have had over the years, there is a feeling that the matroid community (and its relatives) does a better-than-average job of mathematical communication. I don’t think you would have seen much to contradict that belief at this workshop.

It seems as though it has been a good couple of years for matroid and graph research, since a number of people spoke about important new developments, but one such development obviously stands out. Rota’s Conjecture was the outstanding open problem in matroid theory for decades, and its resolution by Jim Geelen, Bert Gerards, and Geoff Whittle is certainly the most significant accomplishment in the field. Geoff gave a talk on one important step in that project. In particular, he talked us through a sketch of the proof that an excluded minor for representability over a finite field must be $f$-connected. That is, if $\mathrm{GF}(q)$ is a finite field, then for every positive integer $k$, there is an integer $n_{q}(k)$ such that whenever $M$ is an excluded minor for $\mathrm{GF}(q)$-representability, and $(A,B)$ is a $k$-separation of $M$, then either $|A|\leq n_{q}(k)$ or $|B|\leq n_{q}(k)$.

Geoff’s talk is complemented by an article in the Notices of the American Mathematical Society. In addition, you can find the slides from many of the conference talks on this page.

Although singling out talks is essentially an impossible task, I will just mention one that I found particularly interesting. Reinhard Diestel reported on work with Sang-Il Oum that provides a meta-theorem about various width parameters. I’ll illustrate the theorem by talking about branch-width and tangles. A branch-decomposition of a matroid or graph is a tree where the non-leaf vertices have degree three, and the leaves are labeled with elements of the ground-set (edge-set). Now each edge of the tree represents a partition of the ground-set into two parts, in other words, a separation. The decomposition has low width if each of those separations has low order. If a matroid does not have low-width branch-decomposition, then we should be able to certify that this is the case. Tangles allow us to do so. A tangle is an orientation of each of the separations of low order. In particular, if we have a tangle, then we have designated a “small” side of each low-order separation. Certain constraints must be satisfied in order for this orientation to be sensible. The most important of these constraints is that three small sides should not cover the entire ground-set between them. Note that in a low-order decomposition, each internal vertex represents a partition of the ground-set into three “small” parts, so a decomposition is a certificate that there can be no tangle, and vice versa. The work by Diestel and Oum generalises these ideas. We choose families of separations, for example the families that might be represented by an internal vertex of a decomposition, and then the theorem guarantees that either there will be a labeled tree where the internal nodes represent members of our chosen families of separations, or else there is some consistent orientation of separations that avoids those families. More details can be found on the arxiv.

At the close of the conference, Stefan extended an invitation to those interested in contributing to this blog, which I will repeat here. If you have an idea for a post, then please get in touch with one of us to discuss it.

Much speculation surrounds the location of the next workshop, two years from now, and multiple suggestions have been made. Expect updates to follow.

Seymour’s 1-flowing conjecture II

In the last post, we had just reached the definition of a 1-flowing matroid. To recap, let $M$ be a matroid on the groundset $E$, and let $e$ be an element of $E$. We choose a function that assigns a positive integral capacity, $c_{x}$, to each element $x\in E-e$. A flow is a function that assigns a non-negative real number, $f_{C}$, to each circuit, $C$, containing $e$. We insist that, for every $x\in E-e$, the inequality $\sum f_{C}\leq c_{x}$ holds (here the sum is taken over all circuits that contains $e$ and $x$). The value of a flow is $\sum f_{C}$, where the sum is taken over all circuits that contain $e$. In the last post, the following inequality was an exercise.

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

(the minimum is taken over all cocircuits $C^{*}$ such that $e\in C^{*}$).

Proof. Let $C^{*}$ be an arbitrary cocircuit that contains $e$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $\mathcal{D}$ be the collection of all ordered pairs $(x,C)$ where $x$ is an element in $C^{*}-e$, and $C$ is a circuit that contains $\{e,x\}$. Since a circuit and a cocircuit cannot intersect in $\{e\}$, it follows that every circuit in $\mathcal{C}$ appears in an ordered pair in $\mathcal{D}$. Therefore

\[
\qquad\sum_{C\in\mathcal{C}}f_{C}\leq\sum_{(x,C)\in\mathcal{D}}f_{C}
=\sum_{x\in C^{*}-e}\sum_{C\in\mathcal{C}\colon x\in C}f_{C}
\leq \sum_{x\in C^{*}-e}c_{x}\qquad\square
\]

We have shown that the value of a flow is bounded above by the capacity of a cut, for every matroid, every element $e$, and every choice of capacities. In some matroids, the inequality is actually an equality for every choice of capacities. In this case, we say that $M$ is $e$-flowing. If $M$ is $e$-flowing for every element $e$, then we say $M$ is $1$-flowing. This definition is motivated by min-max theorems in graph theory, such as the max-flow min-cut theorem. As detailed in the last post, these theorems show that graphic and cographic matroids are $1$-flowing. Seymour’s $1$-flowing conjecture concerns a characterisation of the $1$-flowing matroids.

Bertrand Guenin [Gue02] restates Seymour’s conjecture in a way that I initially did not understand. This method of talking about $1$-flowing matroids involves using ideas from linear programming. Say that $M$ is a matroid on the groundset $E$, and $e$ is an element of $E$. Let $\mathcal{C}$ be the collection of circuits that contain $e$. Let $A$ be the $0$-$1$ matrix whose columns are labelled by elements of $E-e$, and whose rows are labelled by the members of $\mathcal{C}$, where an entry $A_{C,x}$ is equal to one if and only if $x\in C$. Let $\mathcal{P}$ be the set of vectors, $\mathbf{x}$, in $\mathbb{R}^{E-e}$ such that every entry of $\mathbf{x}$ is non-negative, and every entry of $A\mathbf{x}$ is at least $1$. This is the intersection of several half-spaces in $\mathbb{R}^{E-e}$, so $\mathcal{P}$ is a polytope. Guenin’s statement of Seymour’s conjecture rests on the following fact:

Lemma 1. If $M$ is $e$-flowing, then the vertices of $\mathcal{P}$ have $0$-$1$ coordinates.

This wasn’t obvious to me, so I spent some time thinking about why it should be true. My relatively naive proof follows. A more sophisticated argument can be found in Cornuejols [Cor01].

If $\mathbf{a}$ and $\mathbf{b}$ are real vectors with the same number of entries, we write $\mathbf{a}\geq\mathbf{b}$ to mean that every entry of $\mathbf{a}$ is at least as large as the corresponding entry in $\mathbf{b}$. We write $\mathbf{0}$ and $\mathbf{1}$ for the vectors of all zeroes and the vector of all ones, and we use $\mathbb{R}_{\geq 0}$ to denote the set of non-negative reals. Let $\mathbf{c}$ be the vector in $\mathbb{Z}_{+}^{E-e}$ that contains the capacity of each element in $E-e$.

Proposition 1. The value of a maximum flow is equal to
\[
\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}.
\]

Proof. The vector $\mathbf{y}$ assigns a non-negative real value to each circuit containing $e$. The linear program maximises the sum of these values, while respecting the constraint that the sum of the values on circuits passing through an element of $E-e$ must be no greater than the capacity of that element. Thus the solution to the linear program is exactly the maximum value of a flow. $\square$

Proposition 2. The minimum of $\sum_{x\in C^{*}-e}c_{x}$ taken over all cocircuits, $C^{*}$, that contain $e$, is equal to
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}.
\]

Proof. A circuit and a cocircuit cannot meet in a single element. Therefore, if $C^{*}$ is a cocircuit containing $e$, and $C$ is a member of $\mathcal{C}$, then $C^{*}-e$ and $C-e$ have a non-empty intersection. In other words, if $\mathbf{a},\mathbf{b}\in \{0,1\}^{E-e}$ are the characteristic vectors of $C-e$ and $C^{*}-e$ respectively, then $\mathbf{a}^{T}\cdot \mathbf{b} \geq 1$. Thus the dot product of $\mathbf{b}$ with any row of $A$ is at least one. This means that $A\mathbf{b} \geq \mathbf{1}$, so $\mathbf{b}$ is contained in $\{A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. Thus
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}
\leq\\
\min\{\sum_{x\in C^{*}-e}c_{x}\colon C^{*}\ \text{is a cocircuit of}\ M,\ e\in C^{*}\}.
\end{multline*}

For the converse, assume $\mathbf{x}_{0}\in \{0,1\}^{E-e}$ is a solution to the program $\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}$. As the entries of $\mathbf{c}$ are non-negative, we can assume that there is no vector in $\{\mathbf{x}\in\{0,1\}^{E-e}\colon A\mathbf{x} \geq \mathbf{1}\}$ with support properly contained in the support of $\mathbf{x}_{0}$. Therefore $\mathbf{x}_{0}$ is the characteristic vector of a set $D\subseteq E-e$, where $D$ is minimal with respect to meeting every $C\in \mathcal{C}$. We will show that $D\cup e$ is a cocircuit of $M$. Suppose that $D\cup e$ is coindependent. Then there is a basis $B$ of $M$ that has an empty intersection with $D\cup e$. Now $B\cup e$ contains a circuit that contains $e$, and this circuit has an empty intersection with $D$. This is a contradiction, so $D\cup e$ contains a cocircuit $C^{*}$. Suppose that $e\notin C^{*}$, and let $c$ be an arbitrary element of $C^{*}$. By the minimality of $D$, there is a circuit $C \in\mathcal{C}$ such that $C$ has a non-empty intersection with $D$, but not with $D-c$. Then $C$ meets the cocircuit $C^{*}$ in a single element, $c$. This contradiction means that $e\in C^{*}$. As a circuit and a cocircuit cannot meet in a single element, every circuit in $\mathcal{C}$ meets $C^{*}-e\subseteq D$ in at least one element. The minimality of $D$ implies that $C^{*}-e=D$, so $D\cup e$ is a cocircuit, as desired. Now $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to $\sum_{x\in C^{*}-e}c_{x}$, and the proposition follows. $\square$

It follows from Propositions 1 and 2 that $M$ is $e$-flowing if and only if the two programs
\[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\
\mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\]
and
\[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in\{0,1\}^{E-e}\}\]
have the same optimal value for every choice of the vector $\mathbf{c}\in \mathbb{Z}_{+}^{E-e}$.

Let $A’$ be the matrix obtained by stacking a copy of $A$ on top of a copy of the identity matrix $I_{E-e}$. This means that the vector $\mathbf{x}\in\mathbb{R}^{E-e}$ is contained in the polytope $\mathcal{P}$ if and only if it satisfies the following system of inequalities:
\[A’\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}.\]
If $\mathbf{x}$ is a vector in $\mathcal{P}$, then $A’_{\mathbf{x}}$ is the submatrix of $A’$ consisting of all rows $\mathbf{a}^{T}$ satisfying
\[
\mathbf{a}^{T}\mathbf{x}=
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
In other words, $A’_{\mathbf{x}}$ consists of all rows of $A’$ for which the corresponding inequality in the system
\[A’\mathbf{x}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
is actually an equality for the vector $\mathbf{x}$. The vertices of $\mathcal{P}$ can be characterised by saying that they are the vectors $\mathbf{x}\in\mathcal{P}$ such that $A’_{\mathbf{x}}$ contains an $|E-e|\times |E-e|$ non-singular matrix.

Now assume that $\mathcal{P}$ has a vertex that does not have $0$-$1$ coordinates. We will show that $M$ is not $e$-flowing, and this will establish Lemma 1. To this end, assume that $\mathbf{x}_{0}$ is a vertex of $\mathcal{P}$ with at least one coordinate that is not $0$ or $1$. Let $A_{0}$ be an $|E-e|\times |E-e|$ non-singular submatrix of $A_{\mathbf{x}_{0}}$. Let $\mathbf{b}_{0}$ be the submatrix of the vector on the righthand side of
\[A’\mathbf{x}_{0}\geq \begin{bmatrix}\mathbf{1}\\\mathbf{0}\end{bmatrix}\]
consisting of rows that correspond to rows of $A_{0}$. This means that $\mathbf{x}_{0}$ is the unique solution to the equation $A_{0}\mathbf{x}=\mathbf{b}_{0}$. Define $\mathbf{c}^{T}$ to be the sum of the rows of $A_{0}$. Then $\mathbf{c}^{T}\mathbf{x}_{0}$ is equal to the weight of $\mathbf{b}_{\mathbf{x}}$. Let $\mathbf{x}’$ be any point in $\mathcal{P}$ other than $\mathbf{x}_{0}$. Since $\mathbf{x}’$ is not the unique solution to $A_{0}\mathbf{x}=\mathbf{b}_{\mathbf{x}}$, there is some row $\mathbf{a}^{T}$ in $A_{0}$ such that
\[
\mathbf{a}^{T}\mathbf{x}’ >
\begin{cases}
1 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ A\\
0 \quad\text{if}\ \mathbf{a}^{T}\ \text{is a row of}\ I_{E-e}
\end{cases}
\]
This means that $\mathbf{c}^{T}\mathbf{x}’$ is greater than the weight of $\mathbf{b}_{\mathbf{x}}$. It follows that $\mathbf{x}_{0}$ is the unique solution to the linear program
\[
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}
\]
so
\begin{multline*}
\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\
\mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}<\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}, \end{multline*} since $\mathbf{x}_{0}$ is not a $0$-$1$ vector. Now if $\mathbf{y}$ and $\mathbf{x}$ are feasible points in, respectively, the programs \[\max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\] and \[\min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\},\] then $A\mathbf{x}\geq \mathbf{1}$, so $\mathbf{1}^{T} \leq \mathbf{x}^{T}A^{T}$. This means that \[ \mathbf{1}^{T}\mathbf{y} \leq (\mathbf{x}^{T}A^{T})\mathbf{y}= \mathbf{x}^{T}(A^{T}\mathbf{y}) \leq \mathbf{x}^{T}\mathbf{c} = \mathbf{c}^{T}\mathbf{x} \] so \begin{multline*} \max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}\leq\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in(\mathbb{R}_{\geq 0})^{E-e}\}. \end{multline*} (We can also deduce this using linear programming duality.) Combining this with the fact in the last paragraph, we see that \begin{multline*} \max\{\mathbf{1}^{T}\mathbf{y} \colon A^{T}\mathbf{y} \leq \mathbf{c},\ \mathbf{y} \in (\mathbb{R}_{\geq 0})^{\mathcal{C}}\}<\\ \min\{\mathbf{c}^{T}\mathbf{x} \colon A\mathbf{x} \geq \mathbf{1},\ \mathbf{x}\in\{0,1\}^{E-e}\}. \end{multline*} Hence the maximum value of a flow is strictly less than the minimum capacity of a cut, for this choice of the capacity function $\mathbf{c}$. This demonstrates that $M$ is not $e$-flowing, exactly as we wanted. In fact, with a bit more work we can show that the converse also holds. That is, $M$ is $e$-flowing if and only if the vertices of $\mathcal{P}$ all have $0$-$1$ coordinates. [Gue02] B. Guenin, Integral polyhedra related to even-cycle and even-cut matroids. Math. Oper. Res. 27 (2002), no. 4, 693–710. [Cor01] 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.

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.