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.