{"id":843,"date":"2014-06-17T00:35:39","date_gmt":"2014-06-17T04:35:39","guid":{"rendered":"http:\/\/matroidunion.org\/?p=843"},"modified":"2014-06-17T03:32:13","modified_gmt":"2014-06-17T07:32:13","slug":"seymours-1-flowing-conjecture-ii","status":"publish","type":"post","link":"https:\/\/matroidunion.org\/?p=843","title":{"rendered":"Seymour’s 1-flowing conjecture II"},"content":{"rendered":"

In the last post<\/a>, 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<\/em>, $c_{x}$, to each element $x\\in E-e$. A flow<\/em> 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<\/em> 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.<\/p>\n

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

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

Proof.<\/em> 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<\/p>\n

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

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<\/em>. If $M$ is $e$-flowing for every element $e$, then we say $M$ is $1$-flowing<\/em>. 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.<\/p>\n

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:<\/p>\n

Lemma 1.<\/strong> If $M$ is $e$-flowing, then the vertices of $\\mathcal{P}$ have $0$-$1$ coordinates.<\/p>\n

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].<\/p>\n

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$. <\/p>\n

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

Proof.<\/em> 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$<\/p>\n

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

Proof.<\/em> 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
\n\\begin{multline*}
\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\
\n\\mathbf{x}\\in\\{0,1\\}^{E-e}\\}
\n\\leq\\\\
\n\\min\\{\\sum_{x\\in C^{*}-e}c_{x}\\colon C^{*}\\ \\text{is a cocircuit of}\\ M,\\ e\\in C^{*}\\}.
\n\\end{multline*}<\/p>\n

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$<\/p>\n

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

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:
\n\\[A’\\mathbf{x}\\geq \\begin{bmatrix}\\mathbf{1}\\\\\\mathbf{0}\\end{bmatrix}.\\]
\nIf $\\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
\n\\[
\n\\mathbf{a}^{T}\\mathbf{x}=
\n\\begin{cases}
\n1 \\quad\\text{if}\\ \\mathbf{a}^{T}\\ \\text{is a row of}\\ A\\\\
\n0 \\quad\\text{if}\\ \\mathbf{a}^{T}\\ \\text{is a row of}\\ I_{E-e}
\n\\end{cases}
\n\\]
\nIn other words, $A’_{\\mathbf{x}}$ consists of all rows of $A’$ for which the corresponding inequality in the system
\n\\[A’\\mathbf{x}\\geq \\begin{bmatrix}\\mathbf{1}\\\\\\mathbf{0}\\end{bmatrix}\\]
\nis 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.<\/p>\n

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
\n\\[A’\\mathbf{x}_{0}\\geq \\begin{bmatrix}\\mathbf{1}\\\\\\mathbf{0}\\end{bmatrix}\\]
\nconsisting 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
\n\\[
\n\\mathbf{a}^{T}\\mathbf{x}’ >
\n\\begin{cases}
\n1 \\quad\\text{if}\\ \\mathbf{a}^{T}\\ \\text{is a row of}\\ A\\\\
\n0 \\quad\\text{if}\\ \\mathbf{a}^{T}\\ \\text{is a row of}\\ I_{E-e}
\n\\end{cases}
\n\\]
\nThis 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
\n\\[
\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\
\n\\mathbf{x}\\in(\\mathbb{R}_{\\geq 0})^{E-e}\\}
\n\\]
\nso
\n\\begin{multline*}
\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\
\n\\mathbf{x}\\in(\\mathbb{R}_{\\geq 0})^{E-e}\\}<\\\\\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\\n\\mathbf{x}\\in\\{0,1\\}^{E-e}\\},\n\\end{multline*}\nsince $\\mathbf{x}_{0}$ is not a $0$-$1$ vector.\n\nNow if $\\mathbf{y}$ and $\\mathbf{x}$ are feasible points in, respectively, the programs\n\\[\\max\\{\\mathbf{1}^{T}\\mathbf{y} \\colon A^{T}\\mathbf{y} \\leq \\mathbf{c},\\\n\\mathbf{y} \\in (\\mathbb{R}_{\\geq 0})^{\\mathcal{C}}\\}\\]\nand\n\\[\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\\n\\mathbf{x}\\in(\\mathbb{R}_{\\geq 0})^{E-e}\\},\\]\nthen $A\\mathbf{x}\\geq \\mathbf{1}$, so $\\mathbf{1}^{T} \\leq \\mathbf{x}^{T}A^{T}$. This means that\n\\[\n\\mathbf{1}^{T}\\mathbf{y} \\leq\n(\\mathbf{x}^{T}A^{T})\\mathbf{y}=\n\\mathbf{x}^{T}(A^{T}\\mathbf{y}) \\leq\n\\mathbf{x}^{T}\\mathbf{c} =\n\\mathbf{c}^{T}\\mathbf{x}\n\\]\nso\n\\begin{multline*}\n\\max\\{\\mathbf{1}^{T}\\mathbf{y} \\colon A^{T}\\mathbf{y} \\leq \\mathbf{c},\\\n\\mathbf{y} \\in (\\mathbb{R}_{\\geq 0})^{\\mathcal{C}}\\}\\leq\\\\\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\\n\\mathbf{x}\\in(\\mathbb{R}_{\\geq 0})^{E-e}\\}.\n\\end{multline*}\n(We can also deduce this using linear programming duality.) Combining this with the fact in the last paragraph, we see that\n\\begin{multline*}\n\\max\\{\\mathbf{1}^{T}\\mathbf{y} \\colon A^{T}\\mathbf{y} \\leq \\mathbf{c},\\\n\\mathbf{y} \\in (\\mathbb{R}_{\\geq 0})^{\\mathcal{C}}\\}<\\\\\n\\min\\{\\mathbf{c}^{T}\\mathbf{x} \\colon A\\mathbf{x} \\geq \\mathbf{1},\\\n\\mathbf{x}\\in\\{0,1\\}^{E-e}\\}.\n\\end{multline*}\nHence 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.\n\nIn 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.\n\n[Gue02] B. Guenin, Integral polyhedra related to even-cycle and even-cut matroids.\nMath. Oper. Res. 27 (2002), no. 4, 693\u2013710.\n\n[Cor01] G. Cornu\u00e9jols, Combinatorial optimisation: Packing and covering. CBMS-NSF Regional Conference Series in Applied Mathematics, 74. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2001. \n<\/p>\n","protected":false},"excerpt":{"rendered":"

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 … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-843","post","type-post","status-publish","format-standard","hentry","category-matroids"],"_links":{"self":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/843","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=843"}],"version-history":[{"count":35,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/843\/revisions"}],"predecessor-version":[{"id":882,"href":"https:\/\/matroidunion.org\/index.php?rest_route=\/wp\/v2\/posts\/843\/revisions\/882"}],"wp:attachment":[{"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=843"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=843"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/matroidunion.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=843"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}