Short Introduction to application matroid [polymake wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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

<code perl>
> application "matroid";
</code>
from within the ''%%polymake%%'' shell. A permanent setting can be stored with

<code perl>
set_custom $default_application="matroid";
</code>
===== Constructing a Simple Matroid and Playing Around =====

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.

<code perl>
> $M=new Matroid(VECTORS=>[[1,0,0],[1,0,1],[1,1,0],[1,0,2]]);
</code>
If ''%%matroid%%'' is not your default application you have to qualify ''%%Matroid%%'' as in:

<code perl>
> $M=new matroid::Matroid(VECTORS=>[[1,0,0],[1,0,1],[1,1,0],[1,0,2]]);
</code>
Output of basic statistics.

<code perl>
> print $M->N_BASES, " ", $M->N_ELEMENTS, " ", $M->RANK;
> svg($M->LATTICE_OF_FLATS->VISUAL);
3 4 3
</code>
{{ tutorials:release:4.13:apps_matroid:output_0.svg }}
The ''%%VECTORS%%'' are numbered consecutively, starting from zero. The bases are encoded as sets of these ordinal numbers.

<code perl>
> print $M->BASES;
{0 1 2}
{0 2 3}
{1 2 3}
</code>
Similarly you can compute the circuits and cocircuits.

<code perl>
> print $M->CIRCUITS;
{0 1 3}
> print $M->COCIRCUITS;
{2}
{0 1}
{0 3}
{1 3}
</code>
You can also compute other properties, like

<code perl>
> 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
</code>
Even the lattice of flats could be computed and visualised.

<code perl>
> $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}
</code>
===== Matroid Polytopes =====

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<html><Rational></html>.

<code perl>
> 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
</code>
===== Other Constructions =====

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.

<code perl>
> $C=new Matroid(VECTORS=>polytope::cube(3)->VERTICES);
> print $C->N_BASES;
58
</code>
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 [[apps_graph|tutorial on graphs]] for details.

<code perl>
> $G=matroid_from_graph(polytope::cube(3)->GRAPH);
> print $G->N_BASES;
384
</code>
It is also possible to derive a new matroid from others.

<code perl>
> # 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}
</code>
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).

<code perl>
> $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}
</code>
Note that you have to specify N_ELEMENTS when constructing a matroid in this way because this is not implicit in BASES, etc.