The original PDF version was written by Gordon Royle. Transformed into ipynb by Francisco Criado, Daniel Oberländer, Manuel Radons, and Michael Joswig.
A binary matroid $M$ is said to be ${e}$-flowing if for every element $e \in E(M)$, a certain polytope defined using the circuits of $M$ that pass through $e$ has integral vertices. A matroid is called 1-flowing if it is ${e}$-flowing for every element of $E(M)$. In this tutorial-style note, we’ll work through an example, namely the matroid $\operatorname{AG}(3, 2)$ and demonstrate the computational process to checking whether or not it is 1-flowing, using polymake, which is a computer algebra system for polytopes and associated objects.
> application "matroid";
The binary matroid $\operatorname{AG}(3, 2)$ consists of the binary vectors in $\operatorname{PG}(3, 2)$ which lie off a hyperplane (i.e. all the affine points) and so can easily be seen to be represented by the matrix consisting of every column vector with first coordinate equal to one.
> $M = new Matrix<Int>([[1,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,0,1,1,0,0,1,1],[0,1,0,1,0,1,0,1]]); > print $M; 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
The 8 matroid elements (that is, matrix columns) are labeled 0, 1, . . ., 7 in the natural order. Then AG(3, 2) has 14 circuits, all of size 4, as follows:
> $AG32 = new Matroid(BINARY_VECTORS=>cols($M)); > > print $AG32->CIRCUITS; {0 1 2 3} {0 1 4 5} {0 1 6 7} {0 2 4 6} {0 2 5 7} {0 3 4 7} {0 3 5 6} {1 2 4 7} {1 2 5 6} {1 3 4 6} {1 3 5 7} {2 3 4 5} {2 3 6 7} {4 5 6 7}
The automorphism group of $\operatorname{AG}(3,2)$ is transitive on the ground set, and so to check whether the matrix is 1-flowing we only need to test that it is ${0}$-flowing. Each circuit containing 0 yields one constraint on a set of variables identified with $\operatorname{E}(M){0}$, which we will call ${x_1, x_2, \ldots , x_7}$ with the natural correspondence. Each of the circuit constraints is that the sum of the corresponding variables is at least 1. Thus we get the 7 constraints shown in table below.
| Circuit | Constraint |
|---|---|
| $0123$ | $x_1+x_2+x_3\geq 1$ |
| $0145$ | $x_1+x_4+x_5\geq 1$ |
| $0167$ | $x_1+x_6+x_7\geq 1$ |
| $0246$ | $x_2+x_4+x_6\geq 1$ |
| $0257$ | $x_2+x_5+x_7\geq 1$ |
| $0347$ | $x_3+x_4+x_7\geq 1$ |
| $0356$ | $x_3+x_5+x_6\geq 1$ |
In addition to these constraints, each variable must be non-negative, and so we add $x_i \geq 0$ to the list of constraints. These gives us a total of fourteen constraints, each determining a half-space in $\mathbb{R}^7$, and the intersection of these half-spaces is an unbounded polytope; an expression for a polytope in this fashion is called an $H$-representation of the polytope ($H$ for half-space, I suppose).
A polytope can also be described by its vertices or extreme points and, if it is unbounded, its rays in addition. The matroid is ${e}$-flowing if the polytope described above has integral vertices, that is, its vertices have integer coordinates. The description of a polytope by its vertices (and rays) is called its $V$-representation and so the task is to convert the H-representation into the $V$-representation and check integrality.
Several algorithms for this task and their implementations exist. polymake has interfaces to many of them, e.g., cdd by Komei Fukuda. For a survey and extensive comparisons see Assarf et al, Math. Program. Comput. 9.1, pp. 1–38. doi: 10.1007/s12532-016-0104-z.
The basic process is straightforward:
In practice, it is almost as straightforward, with just some possible teething troubles in mastering the syntax of polymake. A constraint in polymake of the form
$$a^T x \geq b$$
(where a is a (column) vector of coefficients, $x$ the vector of variables and $b$ a vector of constants) must first be re-expressed in the form
$$−b + a^T x \geq 0$$
and then the constant term and coefficients in this expression gathered into one row vector in this order, yielding the vector
$$[b, a_1, a_2, \dots , a_n]$$.
The matrix constructed below shows the circuit constraints expressed in polymake form.
> $circuit_constraints = new Matrix([ > [-1,1,1,1,0,0,0,0], > [-1,1,0,0,1,1,0,0], > [-1,1,0,0,0,0,1,1], > [-1,0,1,0,1,0,1,0], > [-1,0,1,0,0,1,0,1], > [-1,0,0,1,1,0,0,1], > [-1,0,0,1,0,1,1,0]]); > > print $circuit_constraints; -1 1 1 1 0 0 0 0 -1 1 0 0 1 1 0 0 -1 1 0 0 0 0 1 1 -1 0 1 0 1 0 1 0 -1 0 1 0 0 1 0 1 -1 0 0 1 1 0 0 1 -1 0 0 1 0 1 1 0
We also need the constraints for non-negativity, but these can be constructed programatically rather than manually because the appropriate matrix is just a zero column vector adjacent to an identify matrix,
> $nonneg_constraints = zero_vector(7) | unit_matrix(7);
and the set of all constraints is obtained from the union of both matrices.
> $all_ineq = $circuit_constraints / $nonneg_constraints;
Let’s just check that all is in order
> print_constraints($all_ineq); 0: x1 + x2 + x3 >= 1 1: x1 + x4 + x5 >= 1 2: x1 + x6 + x7 >= 1 3: x2 + x4 + x6 >= 1 4: x2 + x5 + x7 >= 1 5: x3 + x4 + x7 >= 1 6: x3 + x5 + x6 >= 1 7: x1 >= 0 8: x2 >= 0 9: x3 >= 0 10: x4 >= 0 11: x5 >= 0 12: x6 >= 0 13: x7 >= 0
Finally we can create the polytope and ask for its vertices!
> application "polytope"; > $p = new Polytope<Rational>(INEQUALITIES=>$all_ineq); > > print $p->VERTICES; 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 1/3 1/3 1/3 1/3 1/3 1/3 1/3 1 0 0 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 1 1
Notice that each row listing the vertices has eight coordinates, rather than seven. This is because our $7$-dimensional space has been embedded as the plane $x_0=1$ in an $8$-dimensional space in order to accommodate vertices and rays in a uniform manner. The rows with first coordinate equal to 1 are the vertices, while the others are the rays.
We immediately see that this matroid is not ${0}$-flowing because the point $$(1/3, 1/3, 1/3, 1/3, 1/3, 1/3, 1/3)$$ is a vertex of the associated polytope.
A polytope whose vertices are integral is also called a lattice polytope. If this is satisfied can be checked directly.
> print $p->LATTICE; false
The fact that $AG(3, 2)$ is not $1$-flowing has of course long been known. And because the property of being $1$-flowing is closed under taking minors, this means that no binary matroid with an $AG(3, 2)$ minor is $1$-flowing either.
There are two other known minor-minimal matroids with no $AG(3, 2)$-minor that are not $1$-flowing; these are the dual pair $T_{11}$ and $T_{11}^*$. Seymour conjectured that this is the complete set of excluded minors.
Conjecture. (Seymour) A binary matroid is 1-flowing if and only if it has no $AG(3,2)$, $T_{11}$ or $T_{11}^*$ minor.