user_guide:tutorials:apps_matroid

Differences

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

Link to this comparison view

Both sides previous revision Previous revision
Next revision
Previous revision
user_guide:tutorials:apps_matroid [2019/01/25 09:27]
oroehrig ↷ Links adapted because of a move operation
user_guide:tutorials:apps_matroid [2019/02/04 22:55] (current)
Line 1: Line 1:
-====== Short Introduction to application ''​matroid''​ ======+{{page>​.:​latest:​@FILEID@}}
  
-**This tutorial is also available as a {{ user_guide:​apps_matroid.ipynb |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 
-<​code>​ 
-> application "​matroid";​ 
-</​code>​ 
-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. ​ The matroid is defined by the linear dependence among subsets of these vectors. 
- 
-<​code>​ 
-matroid > $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>​ 
-polytope > $M=new matroid::​Matroid(VECTORS=>​[[1,​0,​0],​[1,​0,​1],​[1,​1,​0],​[1,​0,​2]]);​ 
-</​code>​ 
- 
-Output of basic statistics. 
-<​code>​ 
-matroid > print $M->​N_BASES,​ " ", $M->​N_ELEMENTS,​ " ", $M->​RANK;​ 
-3 4 3 
-</​code>​ 
-{{ user_guide:​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. 
- 
-<​code>​ 
-matroid > print $M->​BASES;​ 
-{0 1 2} 
-{0 2 3} 
-{1 2 3} 
-</​code>​ 
- 
-Similarly you can compute the circuits and cocircuits. 
- 
-<​code>​ 
-matroid > print $M->​CIRCUITS;​ 
-{0 1 3} 
- 
-matroid > print $M->​COCIRCUITS;​ 
-{2} 
-{0 1} 
-{0 3} 
-{1 3} 
-</​code>​ 
- 
-You can also compute other properties, like  
-<​code>​ 
-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 
-</​code>​ 
- 
-Even the lattice of flats could be computed and visualised. 
-<​code>​ 
-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;​ 
-</​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<​Rational>''​. 
- 
-<​code>​ 
-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 
-</​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>​ 
-matroid > $C=new Matroid(VECTORS=>​polytope::​cube(3)->​VERTICES);​ 
- 
-matroid > 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>​ 
-matroid > $G=matroid_from_graph(polytope::​cube(3)->​GRAPH);​ 
- 
-matroid > print $G->​N_BASES;​ 
-792 
-</​code>​ 
- 
-It is also possible to derive a new matroid from others. ​ 
-<​code>​ 
-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} 
-</​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>​ 
-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} 
- 
-</​code>​ 
- 
-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.txt
  • Last modified: 2019/02/04 22:55
  • (external edit)