Short Introduction to application matroid

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 over the rationals. The matroid is defined by the linear dependence among subsets of these vectors.

> $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:

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

Output of basic statistics.

> print $M->N_BASES, " ", $M->N_ELEMENTS, " ", $M->RANK;
> svg($M->LATTICE_OF_FLATS->VISUAL);
3 4

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

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

Similarly you can compute the circuits and cocircuits.

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

You can also compute other properties, like

> print $M->PAVING?"1":"0", " ",
> $M->BINARY?"1":"0", " ",
> $M->SERIES_PARALLEL?"1":"0", " ",
> $M->CONNECTED?"1":"0";
1 1 0 0
> print $M->CONNECTED_COMPONENTS;
{0 1 3}
{2}
> print $M->TUTTE_POLYNOMIAL;
x_0^3 + x_0^2 + x_0*x_1

Even the lattice of flats could be computed and visualised.

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

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.

> print $M->POLYTOPE->VERTICES;
1 1 1 1 0
1 1 0 1 1
1 0 1 1 1
> 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.

> $C=new Matroid(VECTORS=>polytope::cube(3)->VERTICES);
> 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.

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

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

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

> $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]);
> $m=new Matroid(NON_BASES=>$a,N_ELEMENTS=>7);
> 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.