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

This site uses Akismet to reduce spam. Learn how your comment data is processed.