**This tutorial is also available as a jupyter notebook for polymake 3.1.**

This tutorial is meant to show the main features for handling matroids available. To make `matroid`

your current application start `polymake`

with the option `-A matroid`

or use the context switch

> application "matroid";

from within the `polymake`

shell. A permanent setting can be stored with `set_custom $default_application="matroid";`

This is how to produce a matroid from a vector configuration. The matroid is defined by the linear dependence among subsets of these vectors.

matroid > $M=new Matroid(VECTORS=>[[1,0,0],[1,0,1],[1,1,0],[1,0,2]]);

If `matroid`

is not your default application you have to qualify `Matroid`

as in:

polytope > $M=new matroid::Matroid(VECTORS=>[[1,0,0],[1,0,1],[1,1,0],[1,0,2]]);

Output of basic statistics.

matroid > print $M->N_BASES, " ", $M->N_ELEMENTS, " ", $M->RANK; 3 4 3

The `VECTORS`

are numbered consecutively, starting from zero. The bases are encoded as sets of these ordinal numbers.

matroid > print $M->BASES; {0 1 2} {0 2 3} {1 2 3}

Similarly you can compute the circuits and cocircuits.

matroid > print $M->CIRCUITS; {0 1 3} matroid > print $M->COCIRCUITS; {2} {0 1} {0 3} {1 3}

You can also compute other properties, like

matroid > print $M->PAVING?"1":"0", " ", matroid (2)> $M->BINARY?"1":"0", " ", matroid (3)> $M->SERIES_PARALLEL?"1":"0", " ", matroid (4)> $M->CONNECTED?"1":"0"; 1 1 0 0 matroid > print $M->CONNECTED_COMPONENTS; {0 1 3} {2} matroid > print $M->TUTTE_POLYNOMIAL; x*y + y^3 + y^2

Even the lattice of flats could be computed and visualised.

matroid > $lattice=$M->LATTICE_OF_FLATS; matroid > foreach (@{$lattice->nodes_of_rank(2)}){print $lattice->FACES->[$_]," "}; {0 2} {0 1 3} {1 2} {2 3} matroid > print $M->MATROID_HYPERPLANES; {0 1 3} {0 2} {1 2} {2 3} matroid > $M->LATTICE_OF_FLATS->VISUAL;

You can construct a polytope from the bases of a matroid as the convex hull of the characteristic vectors of the bases. This is the *matroid polytope* of that matroid, sometimes also called the *matroid bases polytope*. The matroid polytope of the matroid `$M`

is a subobject `POLYTOPE`

of type `polytope::Polytope<Rational>`

.

matroid > print $M->POLYTOPE->VERTICES; 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 matroid > print $M->POLYTOPE->F_VECTOR; 3 3

The vertices of a polytope give rise to a matroid. Here is an example for the vertices of the three-dimensional regular cube. Notice that point coordinates in the application 'polytope' are given by homogeneous coordinates. Hence this matroid is defined by the relation of affine dependence.

matroid > $C=new Matroid(VECTORS=>polytope::cube(3)->VERTICES); matroid > print $C->N_BASES; 58

The system also allows you to construct a matroid from a graph. The bases correspond to the spanning trees then. Notice that there is more than one way to encode a graph in `polymake`

. Read the tutorial on graphs for details.

matroid > $G=matroid_from_graph(polytope::cube(3)->GRAPH); matroid > print $G->N_BASES; 792

It is also possible to derive a new matroid from others.

matroid > # The arguments are two matroids and for each matroid a basepoint. The basepoints will be identified. matroid > $se=series_extension(uniform_matroid(2,3),0,uniform_matroid(1,3),0); matroid > print deletion($se,4)->VECTORS; 1 0 0 0 1 0 0 0 1 1 1 1 matroid > $pe=parallel_extension(uniform_matroid(1,3),0,uniform_matroid(2,3),0); matroid > print dual(contraction($pe,4))->VECTORS; 1 0 0 0 1 0 0 0 1 1 1 1 matroid > print projective_plane(3)->N_BASES; 234 matroid > print fano_matroid()->N_BASES; 28 matroid > print direct_sum(projective_plane(3),fano_matroid())->N_BASES," = 234*28"; 6552 = 234*28 matroid > print two_sum(uniform_matroid(2,4),0,uniform_matroid(2,4),0)->CIRCUITS; {0 1 2} {3 4 5} {0 1 3 4} {0 1 3 5} {0 1 4 5} {0 2 3 4} {0 2 3 5} {0 2 4 5} {1 2 3 4} {1 2 3 5} {1 2 4 5}

Of course you can also construct your matroid from scratch by specifying, e.g., its set of bases or non-bases and then compute other properties. The following constructs the Fano matroid, which is the simplest matroid that cannot be constructed from a vector configuration (over a field with a characteristic other than two).

matroid > $a=new Array<Set<Int>>([0,1,5],[1,2,6],[0,2,3],[1,3,4],[2,4,5],[3,5,6],[0,4,6]); matroid > $m=new Matroid(NON_BASES=>$a,N_ELEMENTS=>7); matroid > print $m->COCIRCUITS; {0 1 2 4} {0 1 3 6} {0 2 5 6} {0 3 4 5} {1 2 3 5} {1 4 5 6} {2 3 4 6}

Note that you have to specify N_ELEMENTS when constructing a matroid in this way because this is not implicit in BASES, etc.

Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International