user_guide:tutorials:apps_matroid

This tutorial is probably also available as a Jupyter notebook in the demo folder in the polymake source and on github.

Different versions of this tutorial: latest release, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, nightly master

This is an old revision of the document!


Short Introduction to New Application ''matroid''

The application matroid introduced with version 2.9.7 is in its infancy. This tutorial is meant to show the main features 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", " ", $M->BINARY?"1":"0", " ", $M->SERIES_PARALLEL?"1":"0", " ", $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; 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 > $se=series_extension(uniform_matroid(2,3),0,uniform_matroid(1,3),0); # the arguments are two matroids and for each matroid a basepoint.The basepoints will be identified. 

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.

  • user_guide/tutorials/apps_matroid.1495211228.txt.gz
  • Last modified: 2017/05/19 16:27
  • by oroehrig