# 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.

**imports from:**common, graph

**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::BoolWhether 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::StringA 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::BoolWhether 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::FaceLatticeThe 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::IntSize 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 matroid##### Options

Bool dual whether to construct the dual matroid insteadBool check_basis_exchange_axiom whether to perform the check of the axiom after construction##### Returns

Array<Set> **bases_to_revlex_encoding**(bases, r, n) → StringEncode 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 matroid##### Returns

String **check_basis_exchange_axiom**(a) → IntCheck 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 matroid##### Options

Bool verbose print a proof if the given sets do not form the set of bases of a matroid##### Returns

Int is_matroid are the given sets the bases of a matroid?**check_flat_axiom**(a) → IntCheck 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 matroid##### Options

Bool verbose print a proof if the given sets do not form the set of flats of a matroid##### Returns

Int are_flats are the given sets the flats of a matroid?**check_hyperplane_axiom**(a) → IntCheck 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 matroid##### Options

Bool verbose print a proof if the given sets do not form the set of hyperplanes of a matroid##### Returns

Int are_hyperplanes are the given sets the hyperplanes of a matroid?**internal_activity**() → Intcalculate 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) → BoolCheck 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 M##### Options

Bool verbose print diagnostic message in case C is not a modular cut; default is true##### Returns

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) → MatroidCalculate 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 M##### Options

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 true##### Returns

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) → MatroidCreates 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) → MatroidCreates a matroid from the corresponding matroid polytope

*p*.**positroid_from_decorated_permutation**(perm, loops) → MatroidProducing 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**() → MatroidCreates the Fano plane matroid of rank 3 with 7 elements.

Contained in extension`bundled:group`

.##### Returns

Matroid **l8_matroid**() → MatroidThe 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**() → MatroidAn excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

##### Returns

Matroid **n2_matroid**() → MatroidAn excluded minor for the dyadic matroids (see [Oxley:matroid theory (2nd ed.) page 558]).

##### Returns

Matroid **non_fano_matroid**() → MatroidThe 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**() → MatroidCreate 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**() → MatroidThe only other ternary 3-spike apart from the non-Fano matroid. Non binary. Algebraic over all fields.

##### Returns

Matroid **p8_matroid**() → MatroidThe 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**() → MatroidCreate 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**() → MatroidThe rank-3-ternary Dowling Geometry. Representable if and only if the field has not characteristic 2.

##### Returns

Matroid **q8_matroid**() → MatroidA 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**() → MatroidNot representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

##### Returns

Matroid **r9b_matroid**() → MatroidNot representable over any field. Taken from http://doc.sagemath.org/html/en/reference/matroids/sage/matroids/catalog.html

##### Returns

Matroid **t8_matroid**() → MatroidRepresentable 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**() → MatroidA minimal non-representable matroid. An excluded minor for all finite fields with more than four elements. Non-algebraic.

##### Returns

Matroid **wheel4_matroid**() → Matroid