application: matroid
Matroids encode the concept of "(in)dependence" in an abstract way. You can define matroids via vector configurations or graphs, do basic conversions between different descriptions and perform basic operations such as deletions and contractions.
uses: group, ideal, polytope, topaz
Objects
A matroid on the set {0,...,n-1}. Here n is the same as N_ELEMENTS.
Properties of Matroid
- BASES: common::Array<Set<Int>>
Subsets of the ground set which form the bases of the matroid. Note that if you want to define a matroid via its bases, you should also specify N_ELEMENTS, because we allow matroids with loops.
- BINARY_POINTS: common::Matrix<Int, NonSymmetric>
If the matroid is realizable over the field GF(2) with two elements, this property contains coordinates for some realization.
- COCIRCUITS: common::Array<Set<Int>>
Cocircuits (or bonds) of the matroid, i.e., minimal sets intersecting every basis.
- LABELS: common::Array<String>
Unique names assigned to the elements of the matroid.
For a matroid build from scratch, you should create this property by yourself. If you build the matroid with a construction client, (e.g. matroid_from_graph) the labels may be assigend for you in a meaningful way.
- LATTICE_OF_FLATS: graph::FaceLattice
The lattice of flats, this is a graph with all closed sets as nodes
- NON_BASES: common::Array<Set<Int>>
All subsets of the ground sets with cardinality RANK that are not bases.
- N_ELEMENTS: common::Int
Size of the ground set. The ground set itself always consists of the first integers starting with zero.
- POINTS: common::Matrix<Rational, NonSymmetric>
If the matroid is realizable over the rationals, this property contains coordinates for some realization. Specifying coordinates is one way to define a matroid.
- POLYTOPE: polytope::Polytope<Rational>
Polytope whose vertices are the characteristic vectors of the bases.
- REGULAR: common::Bool
Whether the matroid is representable over every field, that is the repesentation is unimodular. NOTE: the property is 'undef' when its hard to decide, whether the matroid is ternary.
- TERNARY: common::Bool
Whether the matroid is representable over GF(3) NOTE: the property is 'undef' when its hard to decide.
- TERNARY_POINTS: common::Matrix<Int, NonSymmetric>
If the matroid is realizable over the field GF(3) with three elements, this property contains coordinates for some realization.
User Functions
- UNDOCUMENTED
- internal_activity () → Int
calculate the internal activity of a base with respect to a given ordering of all bases. Let the given base B = B_j be the j-th one in the given ordering B_1, B_2, ... The internal activity of B_j is the number of "necessary" elements in B_j, i.e., the number of elements i in B_j such that B_j - {i} is not a subset of any B_k, k<j.
Returns
Int - _4ti2Circuits (A) → Matrix
Calculate the circuits of a set of points given as the rows of a Matrix A. The circuits are given as a matrix such that vA=0 for all rows v.
Parameters
Matrix A Matrix containing the points as rows.Returns
Matrix
- UNDOCUMENTED
- contraction (m, element) → Matroid
- direct_sum (m_1, m_2) → Matroid
- parallel_extension (m_1, e_1, m_2, e_2) → Matroid
- parallel_extension (m, e) → Matroid
- series_extension (m_1, e_1, m_2, e_2) → Matroid
- series_extension (m, e) → Matroid
- UNDOCUMENTED
- matroid_from_characteristic_vector (v, r, n) → Matroid
Creates the matroid with a given characteristic plueckervector of rank r and a ground set of n elements.
- matroid_from_graph (g) → Matroid
- matroid_from_matroid_polytope (p) → Matroid
Creates a matroid from the corresponding matroid polytope p.
- UNDOCUMENTED
- fano_matroid () → Matroid
- projective_plane (p) → Matroid
- uniform_matroid (r, n) → Matroid
- UNDOCUMENTED
- matroid_plueckervector (m) → ListReturn
Creates the characteristic- and the rank-plueckervector of a matroid.