user_guide:tutorials:latest:apps_matroid

# Differences

This shows you the differences between two versions of the page.

 — user_guide:tutorials:latest:apps_matroid [2020/01/22 09:02] (current) Line 1: Line 1: + ====== 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";​%%%%''​ + + ===== 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. + + + >$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;​ + 3 4 3 + ​ + {{ :​tutorial:​matroid//​lattice//​of//​flats//​example.png?​nolink&​200|}} 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} + {1 3} + {0 3} + {0 1} + ​ + 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} + {0 2} + {1 2} + {2 3} + >$M->​LATTICE_OF_FLATS->​VISUAL;​ + ​ + ===== 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>​. + + + > 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 + ​ + ===== 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. + + + >$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 [[apps_graph|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. +
• user_guide/tutorials/latest/apps_matroid.txt