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
tutorial:apps_matroid [2017/06/20 17:51] oroehriguser_guide:tutorials:apps_matroid [2019/02/04 22:55] (current) – external edit 127.0.0.1
Line 1: Line 1:
-====== Short Introduction to application ''matroid'' ======+{{page>.:latest:@FILEID@}}
  
-**This tutorial is also available as a {{ :tutorial: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> 
-{{ :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. 
- 
-<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.1497981061.txt.gz
  • Last modified: 2017/06/20 17:51
  • by oroehrig