Differences
This shows you the differences between two versions of the page.
— | user_guide:tutorials:latest:apps_matroid [2023/11/06 10:57] (current) – created - external edit 127.0.0.1 | ||
---|---|---|---|
Line 1: | Line 1: | ||
+ | ====== Short Introduction to application matroid ====== | ||
+ | |||
+ | This tutorial is meant to show the main features for handling matroids available. To make '' | ||
+ | |||
+ | <code perl> | ||
+ | > application " | ||
+ | </ | ||
+ | from within the '' | ||
+ | |||
+ | <code perl> | ||
+ | set_custom $default_application=" | ||
+ | </ | ||
+ | ===== 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=> | ||
+ | </ | ||
+ | If '' | ||
+ | |||
+ | <code perl> | ||
+ | > $M=new matroid:: | ||
+ | </ | ||
+ | Output of basic statistics. | ||
+ | |||
+ | <code perl> | ||
+ | > print $M-> | ||
+ | > svg($M-> | ||
+ | 3 4 3 | ||
+ | </ | ||
+ | {{ tutorials: | ||
+ | The '' | ||
+ | |||
+ | <code perl> | ||
+ | > print $M-> | ||
+ | {0 1 2} | ||
+ | {0 2 3} | ||
+ | {1 2 3} | ||
+ | </ | ||
+ | Similarly you can compute the circuits and cocircuits. | ||
+ | |||
+ | <code perl> | ||
+ | > print $M-> | ||
+ | {0 1 3} | ||
+ | > print $M-> | ||
+ | {2} | ||
+ | {0 1} | ||
+ | {0 3} | ||
+ | {1 3} | ||
+ | </ | ||
+ | You can also compute other properties, like | ||
+ | |||
+ | <code perl> | ||
+ | > print $M-> | ||
+ | > $M-> | ||
+ | > $M-> | ||
+ | > $M-> | ||
+ | 1 1 0 0 | ||
+ | > print $M-> | ||
+ | {0 1 3} | ||
+ | {2} | ||
+ | > print $M-> | ||
+ | x_0^3 + x_0^2 + x_0*x_1 | ||
+ | </ | ||
+ | Even the lattice of flats could be computed and visualised. | ||
+ | |||
+ | <code perl> | ||
+ | > $lattice=$M-> | ||
+ | > foreach (@{$lattice-> | ||
+ | {0 2} {0 1 3} {1 2} {2 3} | ||
+ | > print $M-> | ||
+ | {0 1 3} | ||
+ | {2 3} | ||
+ | {1 2} | ||
+ | {0 2} | ||
+ | </ | ||
+ | ===== 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 '' | ||
+ | |||
+ | <code perl> | ||
+ | > print $M-> | ||
+ | 1 1 1 1 0 | ||
+ | 1 1 0 1 1 | ||
+ | 1 0 1 1 1 | ||
+ | > print $M-> | ||
+ | 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 ' | ||
+ | |||
+ | <code perl> | ||
+ | > $C=new Matroid(VECTORS=> | ||
+ | > print $C-> | ||
+ | 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 '' | ||
+ | |||
+ | <code perl> | ||
+ | > $G=matroid_from_graph(polytope:: | ||
+ | > print $G-> | ||
+ | 384 | ||
+ | </ | ||
+ | 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, | ||
+ | > print deletion($se, | ||
+ | 1 0 0 | ||
+ | 0 1 0 | ||
+ | 0 0 1 | ||
+ | 1 1 1 | ||
+ | > $pe=parallel_extension(uniform_matroid(1, | ||
+ | > print dual(contraction($pe, | ||
+ | 1 1 1 | ||
+ | 1 0 0 | ||
+ | 0 1 0 | ||
+ | 0 0 1 | ||
+ | > print projective_plane(3)-> | ||
+ | 234 | ||
+ | > print fano_matroid()-> | ||
+ | 28 | ||
+ | > print direct_sum(projective_plane(3), | ||
+ | 6552 = 234*28 | ||
+ | > print two_sum(uniform_matroid(2, | ||
+ | {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). | ||
+ | |||
+ | <code perl> | ||
+ | > $a=new Array< | ||
+ | > $m=new Matroid(NON_BASES=> | ||
+ | > print $m-> | ||
+ | {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. | ||
+ | |||