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
These are more complex properties of the matroid.
- BINARY_VECTORS: common::Matrix<Int, NonSymmetric>
If the matroid is realizable over the field GF(2) with two elements, this property contains coordinates for some realization.
- MAXIMAL_TRANSVERSAL_PRESENTATION: common::IncidenceMatrix<NonSymmetric>
If the matroid is transversal (which usually means it was defined with a TRANSVERSAL_PRESENTATION), this is the unique maximal presentation. I.e. the set system consists of RANK many sets and none of the sets can be increased without changing the 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.
- REVLEX_BASIS_ENCODING: common::String
A string listing the bases in revlex order. A '*' means the basis is present, a '0' that it is absent
- SPLITTING_FLACETS: common::Array<Set<Int>>
The facets of the matroid POLYTOPE are either hypersimplex facets or splits induced by flats
- TERNARY: common::Bool
Whether the matroid is representable over GF(3) NOTE: the property may be 'undef' if the current implementation cannot decide.
- TERNARY_VECTORS: common::Matrix<Int, NonSymmetric>
If the matroid is realizable over the field GF(3) with three elements, this property contains coordinates for some realization.
These are properties that form (part of) an axiom system defining a matroid. Most of these can be used to create a 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.
- COCIRCUITS: common::Array<Set<Int>>
Cocircuits (or bonds) of the matroid, i.e., minimal sets intersecting every basis.
- 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.
These are properties of a matroid that count something.
- N_ELEMENTS: common::Int
Size of the ground set. The ground set itself always consists of the first integers starting with zero.
These are properties that can be used to define a matroid, but do not actually constitute an axiom system.
- TRANSVERSAL_PRESENTATION: common::Array<Set<Int>>
A transversal matroid can be defined via a multiset of subsets of the ground set (0,...,n-1) (i.e. N_ELEMENTS needs to be specified). Its bases are the maximal matchings of the bipartite incidence graph.
- VECTORS: 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.
Special purpose properties.
- 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.
User Methods of Matroid
User Functions
Special purpose functions.
- bases_from_revlex_encoding (encoding, r, n) → Array<Set>
Decode the bases of a given matroid from a string containing all possible binom(n,r) tuples of indices in revlex order. If the current tuple is a basis, a '*' is recorded, else a '0'.
Parameters
String encoding the revlex encoding of the list of bases of the matroidInt r the rank of the matroidInt n the number of elements of the matroidOptions
Bool dual whether to construct the dual matroid insteadBool check_basis_exchange_axiom whether to perform the check of the axiom after constructionReturns
Array<Set> - bases_to_revlex_encoding (bases, r, n) → String
Encode the bases of a given matroid as a string. All possible binom(n,r) tuples of indices are traversed in revlex order. If the current tuple is a basis, a '*' is recorded, else a '0'.
Parameters
Array<Set> bases the list of bases of the matroidInt r the rank of the matroidInt n the number of elements of the matroidReturns
String - check_basis_exchange_axiom (a) → Int
Check if a given list of sets satisfies the axioms to be the bases of a matroid.
Parameters
Array<Set> a list of would-be bases of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of bases of a matroidReturns
Int is_matroid are the given sets the bases of a matroid? - check_flat_axiom (a) → Int
Check if a given list of sets satisfies the axioms to be the flats of a matroid.
Parameters
Array<Set> a list of would-be flats of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of flats of a matroidReturns
Int are_flats are the given sets the flats of a matroid? - check_hyperplane_axiom (a) → Int
Check if a given list of sets satisfies the axioms to be the hyperplanes of a matroid.
Parameters
Array<Set> a list of would-be hyperplanes of a matroidOptions
Bool verbose print a proof if the given sets do not form the set of hyperplanes of a matroidReturns
Int are_hyperplanes are the given sets the hyperplanes of a matroid? - 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 - is_modular_cut (M, C) → Bool
Check if a subset of the lattice of flats of a matroid is a modular cut
Parameters
Matroid M the matroidArray<Set> C a list of flats to check if they form a modular cut in MOptions
Bool verbose print diagnostic message in case C is not a modular cut; default is trueReturns
Bool - matroid_plueckervector (m) → List
- minimal_base (matroid, weights) → Set
These functions construct a new Matroid from other objects of the same type.
- contraction (m, element) → Matroid
- direct_sum (m_1, m_2) → Matroid
- free_extension (M) → Matroid
- lex_extension (M, C) → Matroid
Calculate the lexicographic extension of a matroid in a modular cut
Parameters
Matroid M the original matroid to be extendedArray<Set> C a list of flats that form a modular cut in MOptions
Bool check_modular_cut whether to check if C in fact is a modular cut; default is trueBool verbose print diagnostic message in case C is not a modular cut; default is trueReturns
Matroid - parallel_extension (m, e) → Matroid
- series_extension (m, e) → Matroid
These functions construct a new Matroid from other objects.
- 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.
- positroid_from_decorated_permutation (perm, loops) → Matroid
Producing a positroid from a decorated permuatation
With these clients you can create special examples of matroids belonging to parameterized families.
- ag23_matroid () → Matroid
- ag32_matroid () → Matroid
- ag32_prime_matroid () → Matroid
- f8_matroid () → Matroid
- fano_matroid () → Matroid
Creates the Fano plane matroid of rank 3 with 7 elements.
Contained in extensionbundled:group
.Returns
Matroid - l8_matroid () → Matroid
The 4-point planes are the six faces of the cube an the two twisted plannes. Identically self-dual. Representable over all field with more then 4 elements and algebraic over all fields.
Returns
Matroid - n1_matroid () → Matroid
An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
Returns
Matroid - n2_matroid () → Matroid
An excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).
Returns
Matroid - non_fano_matroid () → Matroid
The embedding into the reals of the seven points that define the Fano matroid. Representable if and only if the field has not characteristic 2.
Returns
Matroid - non_p8_matroid () → Matroid
- non_pappus_matroid () → Matroid
Create the matroid encoding the violation of Pappus' Theorem. Not realizable over any field. An excluded minor for all finite fields with more than four elements. Algebraic over all field that do not have characteristic 0.
Returns
Matroid - non_vamos_matroid () → Matroid
- o7_matroid () → Matroid
- oxley_matroids () → Array<Matroid>
Produces many oxley matroids: ag23_matroid, ag32_matroid, ag32_prime_matroid, f8_matroid, j_matroid, l8_matroid, n1_matroid, n2_matroid, o7_matroid, p7_matroid, p8_matroid, non_p8_matroid, pappus_matroid, non_pappus_matroid, pg23_matroid, q3_gf3_star_matroid, q8_matroid, r8_matroid, r9a_matroid, r9b_matroid, r10_matroid, t8_matroid, vamos_matroid, non_vamos_matroid, wheel4_matroid
Returns
Array<Matroid> - p7_matroid () → Matroid
The only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.
Returns
Matroid - p8_matroid () → Matroid
The repesentation over the reals is obtained from a 3-cube where one face is rotated by 45°. Non-representable if and only if the characeristic of the field is 2. Algebraic over all fields.
Returns
Matroid - pappus_matroid () → Matroid
Create the matroid corresponding to Pappus' Theorem. Realizable if and only if the size of the field is not 2,3 or 5. An excluded minor for the field with 5 elements.
Returns
Matroid - pg23_matroid () → Matroid
- projective_plane (p) → Matroid
- q3_gf3_star_matroid () → Matroid
The rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.
Returns
Matroid - q8_matroid () → Matroid
A minimal non-representable matroid. An excluded minor for fields that are not of characteristic 2 or have 3 elements. Non-algebraic.
Returns
Matroid - r10_matroid () → Matroid
- r8_matroid () → Matroid
- r9a_matroid () → Matroid
Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
Returns
Matroid - r9b_matroid () → Matroid
Not representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html
Returns
Matroid - t8_matroid () → Matroid
Representable if and only if the field has characteristic 3. An excluded minor for fields that are not of characteristic 2 or 3.
Returns
Matroid - uniform_matroid (r, n) → Matroid
- vamos_matroid () → Matroid
A minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.
Returns
Matroid - wheel4_matroid () → Matroid