====== Using polymake to Check Whether a Matroid is 1-Flowing ====== The original PDF version was written by [[https://research-repository.uwa.edu.au/en/persons/gordon-royle|Gordon Royle]].\\ Transformed into ipynb by [[http://page.math.tu-berlin.de/~criado/index.html|Francisco Criado]], Daniel Oberländer, [[http://page.math.tu-berlin.de/~radons/|Manuel Radons]], and [[http://page.math.tu-berlin.de/~joswig/|Michael Joswig]]. ==== 1.Introduction ==== 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([[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. [[https://link.springer.com/article/10.1007/s12532-016-0104-z|doi: 10.1007/s12532-016-0104-z]]. ==== 2. The Computation ==== The basic process is straightforward: - Construct a polytope in polymake using the H-representation - Ask polymake to return the $V$-representation. 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(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 ==== 3. Seymour's Conjecture ==== 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.